👦 Blogger introduction: programmer Wula (ULA ~)

✍ Personal warehouse: Code cloud

🔊 Motto: "laziness" is as destructive to a person as it is to get up early.

📚 Disclaimer: big articles are created by bloggers and some articles are sorted on the Internet for learning and knowledge sharing only

💬 Meeting is fate. Now that you come, carry a small bench 🪑 Sit down and chat 👁‍🗨， If you gain something in this article, please don't forget to press one button three times and use your little hand to make a fortune 👍， Your encouragement is the driving force of my creation 🤤!

Sword finger Offer reverse linked list

🤔 subject

Define a function, input the head node of a linked list, invert the linked list and output the head node of the inverted linked list.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

✍ Method 1: iteration (double pointer)

📖 Problem solving ideas

As shown in the figure below, the title requires that the linked list be reversed. All will be implemented using iterative (double pointer) and recursive methods.

Consider traversing the linked list and modifying the next reference when accessing each node

💱 graphic

🧱 code

//  java code
class Solution {
    public ListNode reverseList(ListNode head){
        ListNode cur = head, pre = null;
        
        while (cur != null){
            ListNode tmp = cur.next; 	//Staging subsequent nodes cur next
            cur.next = pre; 		      //Modify the next reference point
            pre = cur; 				    //pre staging cur
            cur = tmp;				  //cur accesses the next node 
        }
        return pre;
    }
}

# python code
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        
        while cur:
            tmp = cur.next # Staging the successor node cur next
            cur.next = pre # Modify the next reference point
            pre = cur      # pre staging cur
            cur = tmp      # cur accessing the next node
            
        return pre
    
    
    
# Using the parallel assignment syntax of Python language, the code can be further simplified (but the readability is reduced):
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
            
        return pre

🎨 Complexity analysis

• Time complexity O(N): traversing the linked list uses linear time.
• Spatial complexity O(1): the variables pre and cur use constant size for additional space.

✍ Method 2: recursion

Consider using recursion to traverse the linked list, terminate the recursion after crossing the tail node, and modify the next reference of each node during backtracking.

📖 Problem solving ideas

recur(cur, pre) recursive function:
1. Termination condition: when cur is empty, the tail node pre is returned (that is, the head node of the inverted linked list);
2. Recursive successor node, and the record return value (i.e. the head node of the inverted linked list) is res;
3. Modify the cur reference of the current node to point to the precursor node pre;
4. Return the header node res of the inverted linked list;

reverseList(head) function: call and return recur(head, null). Null is passed in because the head node points to null after reversing the linked list;

💱 graphic

🧱 code

// java code
class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);    // Call recursion and return
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // Termination conditions
        ListNode res = recur(cur.next, cur);  // Recursive successor node
        cur.next = pre;              // Modify node reference point
        return res;                  // Returns the header node of the inverted linked list
    }
}

# python code
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def recur(cur, pre):
            if not cur: return pre     # Termination conditions
            res = recur(cur.next, cur) # Recursive successor node
            cur.next = pre             # Modify node reference point
            return res                 # Returns the header node of the inverted linked list
        
        return recur(head, None)       # Call recursion and return

🎨 Complexity analysis

• Time complexity O(N): traversing the linked list uses linear time.
• Space complexity O(N): the recursion depth of traversing the linked list reaches N, and the system uses O(N) size for additional space.

If you gain something in this article, please praise it 👍+ Attention, traditional virtues cannot be lost 🙌