This article expands by recursively reversing the entire singly linked list
Recursively reverse the entire list
Let’s look directly at the implementation code:
ListNode reverse(ListNode head) {
if (head.next == null) return head;
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
Copy the code
For recursive algorithms, the most important thing is to define the recursive function. Specifically, our reverse function definition looks like this:
Enter a node head, reverse the list “starting with head”, and return the head node after the reversal.
But there are two caveats:
1, recursive function must have a base case
if (head.next == null) return head;
Copy the code
If there is only one node in the list, it is reversed by itself.
When the list is recursively reversed, the new head node is last, and the previous head node is now the last node.
head.next = null;
Copy the code
Inverts the first N nodes of the linked list
Implement a function like this:
// Reverse the first n nodes of the list (n <= list length)
ListNode reverseN(ListNode head, int n)
Copy the code
ReverseN (head, 3)
The solution is similar to reversing the whole list, as long as a few changes can be:
ListNode successor = null; // Rear drive node
// Reverse n nodes from head and return the new head node
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// Record the n + 1 node
successor = head.next;
returnhead; } Add Java development exchange:484138291Blow water and chat together// Start with head.next and reverse the first n-1 nodes
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// Make the inverted head node connect to the next node
head.next = successor;
return last;
}
Copy the code
Specific differences:
Change the base case to n == 1, invert an element, i.e.
Set head. Next to null, because the original head becomes the last node in the list. But now the head node isn’t necessarily the last node after recursion, so record the successor (the NTH + 1 node), and after inversion join the head.
Reverse part of a linked list
Given an index interval [m,n] (index starting at 1), only the list elements in the interval are reversed.
ListNode reverseBetween(ListNode head, int m, int n)
Copy the code
First of all, if m == 1, it is equivalent to reversing the n elements at the beginning of the list, which is what we just implemented:
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
// Invert the first n elements
return reverseN(head, n);
}
// ...
}
Copy the code
If m! What if theta is equal to 1? If we take the index of head to be 1, then we want to reverse from the MTH element, right; What if the index of head.next is 1? Then, relative to head.next, the inversion interval should start at the m-1st element; What about head.next. Next…
Instead of the idea of iteration, this is the idea of recursion, so we can complete the code:
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// Forward to the start of the reversal triggers the base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
Copy the code
It is worth mentioning that recursively operating on a linked list is not efficient. Compared with the iterative solution, although the time complexity is O(N), the space complexity of the iterative solution is O(1), while the recursive solution requires stack, and the space complexity is O(N).
K sets of reverse lists
ReverseKGroup (head, 2) reverseKGroup(head, 2) reverseKGroup(head, 2) reverseKGroup
If I manage to reverse the first two nodes, what happens to the later ones? These latter nodes are also a linked list, and are smaller in size (length) than the original list. This is called a sub-problem.
We can call reverseKGroup(cur, 2) directly recursively, because the subproblem and the original problem have exactly the same structure, which is called the recursive property.
With the recursion properties discovered, a rough algorithm flow can be obtained:
1. Invert k elements starting with head.
2. Recursively call reverseKGroup with the k + 1 element as head.
3. Connect the results of the two processes.
If I have less than k elements at the end, IT stays the same. So that’s base case
First, we implement a reverse function to reverse the elements within an interval
/** Invert the elements of the interval [a, b]
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
// The condition for terminating while is changed
while(cur ! = b) { nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; }// Return the inverted header node
return pre;
}
Copy the code
Now that we have iteratively implemented the reverse partial list function, we can write the reverseKGroup function as follows:
ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// The interval [a, b] contains k elements to be reversed
ListNode a, b;
a = b = head;
for (int i = 0; i < k; i++) {
// If there are less than k, do not need to reverse, base case
if (b == null) return head;
b = b.next;
}
// Invert the first k elements
ListNode newHead = reverse(a, b);
// Recursively reverse the following lists and join them
a.next = reverseKGroup(b, k);
return newHead;
}
Copy the code
This is what happens when the function recurses:
Determine palindrome lists
The central idea in finding palindrome strings is to expand from the center to both ends:
string palindrome(string& s, int l, int r) {
// Prevent index crossing
while (l >= 0 && r < s.size()
&& s[l] == s[r]) {
// Expand it to both sides
l--; r++;
}
Return the longest palindrome centered on s[l] and s[r]
return s.substr(l + 1, r - l - 1);
}
Copy the code
It’s much easier to determine if a string is a palindrome. You don’t need to worry about parity. You just use the double pointer trick and approach from both ends to the middle:
bool isPalindrome(string s) {
int left = 0, right = s.length - 1;
while (left < right) {
if(s[left] ! = s[right])return false;
left++; right--;
}
return true;
}
Copy the code
Judge palindromic singly linked lists
With the idea of binary tree after order traversal, it is possible to traverse the list in reverse order without explicitly reversing the original list
void traverse(TreeNode root) {
// Preorder traversal code
traverse(root.left);
// In order traversal code
traverse(root.right);
// The code is traversed sequentially
}
Copy the code
With the idea of binary tree after order traversal, it is possible to traverse the list in reverse order without explicitly reversing the original list
void traverse(TreeNode root) {
// Preorder traversal code
traverse(root.left);
// In order traversal code
traverse(root.right);
// The code is traversed sequentially
}
Copy the code
Linked lists can also have preordered traversal and postordered traversal:
void traverse(ListNode head) {
// Preorder traversal code
traverse(head.next);
// The code is traversed sequentially
}
Copy the code
If I want to print the val value in the list in order, I can write the code in the preorder traversal position. Conversely, if you want to traverse the list in reverse order, you can do this by traversing the positions in post order:
/* Print the elements in the list in reverse order */
void traverse(ListNode head) {
if (head == null) return;
traverse(head.next);
// The code is traversed sequentially
print(head.val);
}
Copy the code
In fact, can be slightly modified to mimic the double pointer to achieve palindrome judgment function:
// Left pointer
ListNode left;
boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) return true;
boolean res = traverse(right.next);
// The code is traversed sequentially
res = res && (right.val == left.val);
left = left.next;
return res;
}
Copy the code
The core logic of doing this is to actually put the list nodes on a stack and then take them out again, in reverse order, but we’re using a stack of recursive functions.
Optimizing space complexity
1. Find the midpoint of the list by using the fast and slow Pointers in the “double pointer Technique” :
ListNode slow, fast;
slow = fast = head;
while(fast ! = null && fast.next ! = null) { slow = slow.next; fast = fast.next.next; }// The slow pointer now points to the midpoint of the list
Copy the code
If the fast pointer does not point to null, the list length is odd, and slow is further:
if(fast ! = null) slow = slow.next;Copy the code
3. Reverse the list from slow. Now you can start comparing palindromes:
ListNode left = head;
ListNode right = reverse(slow);
while(right ! = null) {if(left.val ! = right.val)return false;
left = left.next;
right = right.next;
}
return true;
Copy the code
Putting the above three pieces of code together effectively solves this problem, where the reverse function is easy to implement:
ListNode reverse(ListNode head) {
ListNode pre = null, cur = head;
while(cur ! = null) { ListNode nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; }return pre;
}
Copy the code
The overall code is as follows:
// This method works by reversing the list in the middle. Since it is not easy to iterate over the list in the back, it is equivalent to traversing the original list in the back, which makes it easier to compare the list in the front
public boolean isPalindrome(ListNode head) {
ListNode slow = findMidNxt(head);
ListNode left = head;
// Reverse the list in the middle, so that it is convenient to iterate over the list to determine whether the list and the left are the same
ListNode right = reverse(slow);
while(right! =null) {if(right.val! =left.val) {return false;
}
right = right.next;
left = left.next;
}
// left = head;
return true;
}
// Reverse the list
public ListNode reverse(ListNode head) { ListNode pre,cur,nxt; pre = null; cur = head; nxt =head;while(cur! =null) { nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; }return pre;
}
// Use the speed pointer to find the node after the middle node
public ListNode findMidNxt(ListNode head) { ListNode slow,fast; slow = head; fast = head;while(fast! =null&&fast.next! =null) { slow = slow.next; fast = fast.next.next; }// If the fast pointer does not point to null, the list length is odd and slow has to go one step further
if(fast ! =null) { slow = slow.next; }return slow;
}
Copy the code
Although this method is efficient, it destroys the original structure of the input list. Can this flaw be avoided?
In fact, this problem is easy to solve, the key is to get the two pointer positions p, q:
To restore the list order, simply add a line of code before return:
p.next = reverse(q);
Copy the code
conclusion
Look for palindrome string from the middle to both ends of the extension, judge palindrome string from both ends to the middle of the contraction. For the single linked list, can not directly reverse traversal, can create a new reverse list, can use the list after the order traversal, can also use stack structure reverse processing single linked list.
As for palindrome linked list judgment, due to the particularity of palindrome, the linked list can not be completely reversed, but only part of the list can be reversed, reducing the space complexity to O(1).
Classification: Data structures