206. Reverse linked lists

Topic describes

Given the head node of a single-linked list, reverse the list, and then return the reversed list.

The sample

Example 1

Enter: head = [1.2.3.4.5] output: [5.4.3.2.1]
Copy the code

Example 2

Enter: head = [1.2] output: [2.1]
Copy the code

Their thinking

Take the following linked list as an example:

1 -> 2 -> 3 -> null
Copy the code

Our expected results are:

null <- 1 <- 2 <- 3
Copy the code

  • Following the example above, the general idea is to reverse adjacent next Pointers

  • So we can define a prev pointer that points to the previous node

  • Define a cur pointer to the current node

  • Then we point cur’s Next to Prev

    • // Set prev to null and cur to 1
prev cur
null 1 -> 2 -> 3 -> null

// Cur.next = prev, reverse the list, and move the pointer back
// prev = 1, cur = 2
       prev cur
null <- 1 -> 2 -> 3 -> null


// prev = 2, cur = 3
	    prev cur
null <- 1 <- 2 -> 3 -> null

// prev to 3, cur to null
	        prev cur
null <- 1 <- 2 <- 3 -> null
Copy the code

    • When the cur pointer reaches the tail node, the prev pointer points to the head node of the reversed list, so return prev

  • But we have to pay attention to one detail

    • cur.next = prev
Copy the code

    • When we point next of the current pointer to the previous node, we can’t follow the path without first saving the next node of the current node

    • So we’ll also introduce a Next that points to the next node after the current node

  • That’s pretty clear. Go code.

code

var reverseList = function (head) {
  // Let's define it as required
  let prev = null;
  let cur = head;
  // If the current node is not the last node, I will not stop
  while (cur) {
    // Temporarily store the next node of the current node
    const next = cur.next;
    / / reverse
    cur.next = prev;
    // Move back one bit
    prev = cur;
    cur = next;
  }
  // Finally return prev
  return prev;
};
Copy the code