Shulou(Shulou.com)06/01 Report--

This article mainly shows you "LeetCode how to reverse the linked list", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "LeetCode how to reverse the linked list" this article.

Topic description

Reverses a single linked list.

Example:

Enter: 1-> 2-> 3-> 4-> 5-> NULL

Output: 5-> 4-> 3-> 2-> 1-> NULL

Problem-solving ideas

Linked lists are generally solved by iterative or recursive methods, and generally construct double-pointer or three-pointer, such as inverted linked list or DP dynamic programming.

Double pointer iteration

We can request two pointers. The first pointer is called pre, which initially points to null.

The second pointer, cur, points to head, and then iterates through cur.

Each iteration to cur points the next of cur to pre, and then pre and cur move forward one bit.

When the iteration is over (cur becomes null), pre is the last node.

Java implementation

Class Solution {

Public ListNode reverseList (ListNode head) {

/ / Application node. Pre and cur,pre point to null.

ListNode pre = null

ListNode cur = head

ListNode tmp = null

While (curvilinear null) {

/ / record the next node of the current node

Tmp = cur.next

/ / then point the current node to pre

Cur.next = pre

/ / both pre and cur nodes move forward one bit.

Pre = cur

Cur = tmp

}

Return pre

}

}

Python implementation

Class Solution (object):

Def reverseList (self, head):

If not head or not head.next:

Return head

L = head

R = head.next

Remain = r.next

L.next = None

While r:

R.next = l

L = r

R = remain

If remain:

Remain = remain.next

Return l

Recursive implementation:

Two conditions for recursion:

The termination condition is that the current node or the next node = = null inside the function, change the direction of the node, that is, the next node of head points to the head recursive function, the sentence head.next.next = head is very difficult to understand, in fact, the next node of head points to head.

In fact, the cur returned each time in the recursive function is only the last node. Inside the recursive function, the direction of the current node is changed.

Class Solution {

Public ListNode reverseList (ListNode head) {

/ / Recursive termination condition is currently empty, or the next node is empty

If (head==null | | head.next==null) {

Return head

}

/ / the cur here is the last node

ListNode cur = reverseList (head.next)

/ / if the linked list is 1-> 2-> 3-> 4-> 5, then the cur is 5

/ / while head is 4, the next one is 5, the next one is empty.

/ / so head.next.next is 5-> 4

Head.next.next = head

/ / to prevent linked list loops, head.next needs to be set to empty

Head.next = null

/ / each layer recursive function returns cur, that is, the last node

Return cur

}

}

# Definition for singly-linked list.

# class ListNode:

# def _ _ init__ (self, x):

# self.val = x

# self.next = None

Class Solution:

Def reverseList (self, head: ListNode)-> ListNode:

If not head or head.next = = None: return head

Res = self.reverseList (head.next)

Head.next.next = head

Head.next = None

Return res

The above is all the contents of the article "how to reverse the linked list of LeetCode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.