“This is the 29th day of my participation in the August Gwen Challenge.

Topic describes

Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list.

Example:

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

Limitations:

0 <= Number of nodes <= 5000

Answer key

Use of external space

Apply for a dynamically expanded array or container, such as an ArrayList, and iterate through the list to add elements to the container. Use the container’s own API to reverse the entire container, so that the reverse effect is achieved. Finally, we iterate through both the container and the list, changing the list value to the container value. Because the value of the container is 5, 4, 3, 2, 1. The list is reconfigured in that order, and it’s done.

Spatial complexity

O(N)

Double pointer method

Algorithm thought

We apply for two Pointers, one called pre, which initially points to NULL. The second pointer, cur, points to head and iterates over cur. In each iteration cur points cur’s Next to Pre, and then Pre and Cur advance one place. After iterating (cur null), pre is the last node.

code

Class Solution {public ListNode reverseList(ListNode head) {pre = null; ListNode cur = head; ListNode tmp = null; while(cur! =null) {// Record the next node of current node TMP = cur.next; // Then point the current node to pre cur.next = pre; // the pre and cur nodes advance one pre = cur; cur = tmp; } return pre; }}Copy the code

Personal understanding

Iterate through the list, changing the value to which next points for each node. So what’s the new next value of a node? It’s the previous node, so we can just save it, and we can retrieve it when we use it, so we define the pre node. So when should we assign the next node of the current node? We cannot directly execute the following code: head. Next = pre; You can’t do that. It’s a closed loop. So we have a temporary variable TMP, which stores the value of next for the current node. First fetch the value of head.next, then assign the value of head.next to pre, and then assign the value of TMP to head. Can we obtain the last set of nodes through the head node? Because our head node is the next value of the last node, it is null, so we take the value of head.

The code above uses cur instead of head.

The recursive method

Algorithm thought

Two conditions for recursion:

  1. The termination condition is either the current node or the next node == NULL
  2. Inside the function, change the direction of the node, that is, the next node of the head points to the head recursive function
head.next.next = head
Copy the code

code

Class Solution {public ListNode reverseList(ListNode head) { Or the next node is empty if (head = = null | | head. The next = = null) {return head; } ListNode cur = reverseList(head.next); // If the list is 1->2->3->4->5, the cur is 5 and the head is 4, the next head is 5 and the next one is empty. Next = null; // Head. Next = null; // Each level of the recursive function returns a cur, that is, the last node return cur; }}Copy the code

Personal understanding

Why are there two termination conditions?

There are two cases:

  1. The linked list is empty and needs to be determinedhead==null
  2. Normal linked list, need to judgehead.next==null

head.next.next = headHow to understand?

Next is the next node of the current node, and the next value of this node is the reverse, head

head.next = nullWhat does that mean?

To prevent closed loop.

Why return cur? Since cur is the value returned by the last level of recursion, which is the last node, and the first node in the inversion list, we just return this node.

Subject to the original

Author: Wang_ni_MA Link: leetcode-cn.com/problems/fa… Source: LeetCode