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