Reverse a linked list

Take a one-way list, reverse it, and return the reversed list. Example: 1->2->3->4->5 converts to 5->4->3->2->1

Idea 1: Define multiple Pointers for interchangeability

  1. Let’s define three Pointers: pre (head of the unreversed list) cur (head of the unreversed list) Next (next bit of the unreversed list)
  2. The first step is to make pre point to empty, CUR point to the current head node, and Next point to the next node of the current cur.
  3. The second step is to have cur point to pre, then move pre to cur, cur to Next, and Next to the next node
  4. Repeat the second step until the list reaches the end, and then return pre to reverse the list.

Idea 1: JS code implementation

var reverseList = function(head) {
  if(! head)return null;
  let pre = null; // Reverse the header of the list
  let cur = head; // No reverse header
  let next = head.next; // Next node
  while (cur) {
    cur.next = pre; // The next bit of the current node points to pre
    pre = cur; // Pre moves to the current list head node
    cur = next; // Move the current head node one bit back
    next && (next = next.next) // If the next bit is not empty, the list still has a value, and the next bit moves one more bit, thus completing a node inversion and continuing the loop until the list ends.
  }
  return pre; // return the reverse list header
};
Copy the code

Idea 2: Recursion

When switching, the current node is assigned to the next node after the switching node.

Idea 2: code implementation

var reverseList = function(head) {
  if(! head)return head; // If the list is empty, return the current list
  if(! head.next)return head; // If the list has only one digit, the current list is also returned
  let next = head.next; // Next node
  let p = reverseList(head.next); // Get the inverted list head node
  head.next = next.next; // Reverse the current node
  next.next = head; // Connect the next node back to the current head node (1, 2, 3), the current node is 2, then connect 3->2, finally connect 1 to 2, then connect 3->2->1
  return p;
};
Copy the code