This is the 14th day of my participation in the August Text Challenge.More challenges in August

206, Reverse Linked List

The question:

Given the head of a singly 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

Constraints:

  • The number of nodes in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

Problem solving:

There are many ways to implement, it is best to list a variety of implementation, and then analyze the time complexity, focusing on the understanding of the problem and the application of basic knowledge.

1, sequential traversal of the list to store nodes on the stack, and then all the way out of the stack to build new list nodes.
2. Iterate through the linked list, create new nodes according to the nodes traversed, and build a new linked list.

Reverse linked list method: create a new node object, to ensure the integrity of the parameter, high space complexity

 public static ListNode reverseListNode(ListNode head) {
     // Build a cursor node to be the transition node of the upper and lower nodes
     ListNode resultHeadNode = null;
 ​
     while(head ! =null) {
         resultHeadNode = new ListNode(head.value, resultHeadNode);
         head = head.next;
     }
 ​
     return resultHeadNode;
 }
Copy the code
Iterate through the linked list, creating multiple references to receive the traversed nodes and gradually changing the pointing relationship of these nodes.

Lower space complexity implementation, do not create new node objects, change the old node pointing relationship

Instead of creating nodes, use existing nodes and change the direction between nodes

Experience in doing problems: especially for algorithm problems, work out the basic logic on paper and think clearly about the code implementation logic (in fact, this is the difficulty)

Do linked list related problems to clarify the front-end nodes and back-end nodes, the rest is easy

 public static ListNode reverseListNode1(ListNode head) {
     // Create a cursor node to transfer node data
     ListNode resultHeadNode = null;
     ListNode currentNode;
     while(head ! =null) {// Replace the head node
         currentNode = head;
         head = head.next;
 ​
         // Point the next cursor node to the result header node, and then point the result header node reference to the cursor node object
         currentNode.next = resultHeadNode;
         resultHeadNode = currentNode;
     }
 ​
     return resultHeadNode;
 }
Copy the code