“This is the 22nd day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

Given the head node of a single linked list, reverse the list and return 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

Tip:

  • The number of nodes in a linked list ranges from[0, 5000]
  • -5000 <= Node.val <= 5000

Advanced: Lists can be reversed iteratively or recursively. Can you solve the problem in two ways?

Answer key 1

  1. If the list is empty or the list has only one node, return to the original list
  2. To define apreThe pointer points to the list head node
  3. To define anextInitialize the pointer to the head node, and then letnextThe pointer moves backwards, and in the process moves the next node’spreProperty points to the previous node until you reach the end of the list
  4. exchangeheadPointers andnextPointer to the value and letheadThe needle goes back,nextThe Pointers move forward, swapping the values of the two nodes again until the two Pointers meet
  5. Return to the head node

The overall process is as follows:

The code is as follows:

Var reverseList = function (the head) {/ /, sentenced to the if (head = = = null | | head. The next = = = null) return the head; let pre = head,next = head; While (Next-next){next-next-pre = next; next = next.next; } // When two Pointers do not want to cross, swap the values of the two Pointers and make them move towards the middle while(pre! ==next && next.next! ==pre){ const nextVal = next.val; next.val = pre.val; pre.val = nextVal; pre = pre.next; next = next.pre; } return head; };Copy the code

Answer key 2

  1. If the list is empty or the list has only one node, return to the original list
  2. To define apreThe pointer points to the list head node
  3. To define anextThe pointer initializes pointinghead.nextwhennextWhen the pointer is not null, willnext 的 preAttribute points topreAnd thenprePointer,nextThe hands went backwards together
  4. whennextPointer tonullThe time,prePointer to the last node in the list, updatenext = pre
  5. whennext.preIf the value is not empty, modify itnext.nextPointer tonext.preTo reverse the linked list
  6. whennext.preIs empty,nextPoints to the head node and sets the head nodenextPoint to thenull
  7. The lastpreThe last node of the previous list to which the pointer points is the head node of the reversed list

The overall process is as follows:

The code is as follows:

Var reverseList = function (the head) {/ /, sentenced to the if (head = = = null | | head. The next = = = null) return the head; let pre = head, next = head.next; While (next){next. Pre = pre; pre = pre.next; next = next.next; } // Change next pointer from back to front to complete list inversion next = pre; while(next.pre){ next.next = next.pre; next = next.next; } // next points to null next. Next = null; // the last node of the previous list is the first node of the reversed list. };Copy the code

Answer key 3

The solution method of problem solving 2 can be further optimized, and the list inversion can be completed by traversing it once

The solution is as follows:

  1. If the list is empty or the list has only one node, return to the original list
  2. defineprePointer to the head node,nextPointer tohead.next
  3. Will the head nodenextModified tonull
  4. willnext 的 nextPointer topreAnd thenpre 和 nextTake a step back together untilnextPoint to the last node of the list, at this point, the node is the head node of the list after bit inversion, return to the node can be

The overall process is as follows:

The code is as follows:

Var reverseList = function (the head) {/ /, sentenced to the if (head = = = null | | head. The next = = = null) return the head; Let pre = head, next = head. Next; Next = null; // Set next to null for the head node because the head node is the last node of the reversed list. While (next){const next_next = next-.next; // When next is not empty, make the next pointer to the next node point to the previous node. next.next = pre; pre = next; next = next_next; } // return the last node of the original list, i.e. the first node of the reversed list. };Copy the code

At this point we have completed the Leetcode-206-reverse linked list

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