LeetCode algorithm problem 206: Reverse linked lists

Topic describes

Give you a single linked list head, ask you to reverse the list, and return the reversed list.


Example 1:

Input: head = [1, 3] Output: [3, 1]Copy the code

Example 2:

Input: head = [1, 3, 4, 6, 9]Copy the code

Example 3:

Input: head = [] Output: []Copy the code

Solution method (I) : double pointer iteration method

Train of thought
  • We first define two Pointers, curr and prev, where curr refers to the current node with an initial value of head and prev refers to its previous node with an initial value of NULL. Go one step at a time until Curr gets to the end of the list, using next to save the next node from the current node
  • At each step, curr’s next points to Prev, thus completing a reversal
  • Assign the next node of the current node to the current node, and assign the updated current node to its previous node prev, that is, prev points to curr, and curr points to the next node of curr
code
function reverseList(head) {
  let curr = head;       // The current node is curr
  let prev = null;       // Prev is the previous node of the current node
  while(curr) {
    // Save the next node of the current node to next
    const next = curr.next;
    curr.next = prev;
    // Update the prev node iteratively
    prev = curr;
    // Update the curr node iteratively
    curr = prev;
  }
  return prev;
}
Copy the code
Complexity analysis

Time complexity O(n), space complexity O(1)

Solution method (2) : recursive method

Train of thought
  • Recursively to the last node in the list
  • The next pointer of the next node of the current node points to the current node. Since the inversion should not point to the right, we need to break the next pointer of the current node to null
  • Returns the current node until the recursion ends
code
var reverseList = function(head) {
  Head ==null; head==null; head==null
  Next ==null; return the last element of the list
  if(head==null || head.next==null) {
    return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null
  return newHead;
}
Copy the code
Complexity analysis

Time complexity and space complexity are both O(n).


The last

If it helps you, please like and bookmark this article and let more people see it ~ (“▔□▔)/

If you have any objections, please leave them in the comments section and I will reply one by one

If you are interested, please visitA blogger with a light in his eyes