“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

[B] [C] [D]

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

Example 1:

Input: head = [1,2,3,4,5] output: [5,4,3,2,1]Copy the code

Example 2:

Input: head = [1,2] output: [2,1]Copy the code

Example 3:

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

Let’s talk about the first method:

  1. Initialize a variable vhead = null;

  2. Create a new linked list node, val = val of the current node, next to vhead, vhead = node, and loop to know the end of the list

  3. Finally, return to vhead

At this point, our first solution is complete, the following is the code implementation

var reverseList = function(head) {
    let vhead = null,
    cur = head;
    while(cur){
        const node = new ListNode(cur.val);
        node .next = vhead;
        vhead = node;
        cur = cur.next;
    }
    return vhead;
}
Copy the code

However, with the above method, we create a corresponding number of nodes and create extra storage space to store the resulting linked list. Is there a way to flip the linked list by directly operating on the original list?

Here’s the second method:

  1. The linked list given in the question is a one-way linked list. We can adjust the linked list to a two-way linked list, i.e., previously there was one for each nodenextProperty points to its next node. The list traverses only from the beginning node to the end nodenextThere’s another propertypreProperty (or whatever it’s called) that points to its last node
  2. And then we define two Pointers,prePointing to the head node,nextPoint to the end, swap the values of the two Pointers, andpreMove back one,nextMove one bit forward and swap the values of the two Pointers until they meet
  3. The last returnheadThe node can be

At this point, our second way of thinking is complete, the following is the code implementation

var reverseList = function(head) { if(head === null) return null; let pre = head, next = head.next; while(next){ next.pre = pre; pre = pre.next; next = next.next; } next = pre,pre = head; while(next ! == pre && pre.pre ! == next){ const nextVal = next.val; next.val = pre.val; pre.val = nextVal; pre = pre.next; next = next.pre; } return head; }Copy the code

If you have any questions or suggestions, please leave a comment!