👦 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 🙌