After reading this article, you can try to solve the following questions:

25. Flip linked lists in groups of K

———–

The previous article “recursively reverse part of a linked list” explains how to recursively reverse part of a linked list. Some readers ask how to iteratively reverse a linked list. The problem solved in this article also needs to reverse the function of a linked list.

This paper is to solve the “K group of reverse linked lists”, it is not difficult to understand:

This problem is often seen in interviews, and LeetCode is Hard. Is it really that Hard?

For the basic data structure algorithm problem is not difficult, as long as the combination of characteristics a little bit of disassembly analysis, generally no difficulty. Let’s take that apart.

First, analyze the problem

First of all, as mentioned in the framework of data structure learning, linked list is a data structure with both recursive and iterative properties. If you think about it carefully, you can find that this problem has recursive properties.

What do you mean by recursive properties? For example, we call reverseKGroup(head, 2) to reverse the list with two nodes:

If I manage to reverse the first two nodes, what do I do with the next ones? The following nodes are also a linked list, and smaller in size (length) than the original list. This is called a sub-problem.

We can recursively call the reverseKGroup(cur, 2) directly because the subproblem and the original problem have exactly the same structure, which is called recursive property.

After discovering the recursive properties, the general algorithm flow can be obtained:

1. Invert k elements starting with head.

2. ReverseKGroup is recursively called on the k + 1 element as the head.

3. Connect the results of the two processes.

So that’s the whole idea, and the last thing to notice is that recursive functions have a base case, so what’s the problem with this?

And they say, if the last element is less than k, it stays the same. So that’s the base case, and we’ll do that in the code.

Two, code implementation

First, we implement a reverse function to reverse elements within an interval. Before we do that, let’s simplify a little bit. Given a list head, how do we reverse the entire list?

// Reverse the list starting with a
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while(cur ! =null) {
        nxt = cur.next;
        // reverse node by node
        cur.next = pre;
        // Update the pointer position
        pre = cur;
        cur = nxt;
    }
    // return the inverted header
    return pre;
}
Copy the code

This time, using an iterative approach, it should be easy to understand with animation.

“Reverse a linked list with a head” is actually “reverse a to NULL”, so if you were asked to “reverse a to B”, would you?

Simply change the function signature and change null to b in the code above:

/** inverts the elements of the interval [a, b], note that it is left closed and right open */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // Change the terminating condition of the while
    while(cur ! = b) { nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; }// return the inverted header
    return pre;
}
Copy the code

PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.

Now that we have iterated through the partially reversed list, we can write the reverseKGroup function using the same logic as before:

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++) {
        // There is no need to reverse the base case
        if (b == null) return head;
        b = b.next;
    }
    // Invert the first k elements
    ListNode newHead = reverse(a, b);
    // Recursively invert subsequent lists and join them
    a.next = reverseKGroup(b, k);
    return newHead;
}
Copy the code

To explain a few lines of code following the for loop, note that the reverse function reverses the interval [a, b], so it looks like this:

The recursive part of the function is not expanded, and when the recursive part of the whole function is completed, this result is exactly what the problem means:

Three, the last word

In terms of reading volume, algorithm-related articles on basic data structures are not widely read, which I would say is to be lost.

People like to look at questions about dynamic programming, probably because it’s so common in interviews, but as FAR as I’m concerned, a lot of algorithmic ideas are rooted in data structures. One of the famous works of our public account, “Framework thinking of Learning Data Structure” mentioned, what dynamic gauge, backtracking, divide-and-conquer algorithm, in fact, are tree traversal, tree this structure it is not a multi-fork linked list? You can handle basic data structure problems, and solving general algorithm problems shouldn’t be too difficult.

So how do you break things down and discover recursion? This can only be more practice, maybe the follow-up can write a special article to discuss it, this article so far, I hope to help you!

＿＿＿＿＿＿＿＿＿＿＿＿＿

My online e-book has 100 original articles, hand handle with brush 200 force buckle topic, suggest collection! The corresponding GitHub algorithm repository has been awarded 70K Star, welcome standard star!