How to make a set of K reverse linked lists

After reading this article , You can go and get the following questions ：

25.K A set of flip list

-----------

Previous post 「 Recursively reverses a part of a linked list 」 How to recursively reverse a part of a linked list , Some readers ask how to iteratively reverse the linked list , The problem that this article solves also needs to reverse the function of linked list , We may as well use the iterative method to solve .

This article is to solve 「K A set of reverse linked list 」, It's not difficult to understand. ：

This problem is often seen in face sutras , and LeetCode The difficulty is Hard, Is it really that hard ？

The algorithm of basic data structure is not difficult , As long as the combination of characteristics a little bit disassembly analysis , Generally, there is no difficulty . Now let's take this problem apart .

One 、 To analyze problems

First , above Frame thinking of learning data structure Mentioned , Linked list is a data structure with recursive and iterative properties , If you think about it carefully, you can find that This problem is recursive .

What is recursive property ？ Just look at the picture above , For example, we call the linked list reverseKGroup(head, 2), That is to 2 Nodes are a set of inverted linked lists ：

If I try to put the front 2 Nodes reversed , How to deal with the nodes at the back ？ The following nodes are also a linked list , And the scale （ length ） It's smaller than the original list , This is called Sub problem .

We can call... Directly recursively reverseKGroup(cur, 2), Because the structure of the subproblem and the original problem are exactly the same , This is the so-called recursive property .

Found the recursive property , We can get the general algorithm flow ：

1、 First reverse to head At the beginning k Elements .

2、 Will be the first k + 1 Elements as head Recursively call reverseKGroup function .

3、 Connect the results of these two processes .

The whole idea is like this , The last thing to note is , Recursive functions have a base case, What's the problem ？

It's a question , If the final element is not enough k individual , Keep it the same . This is it. base case, It'll be reflected in the code later .

Two 、 Code implementation

First , We want to achieve one reverse Function reverses the elements within an interval . Before that, let's simplify , Given the chain header node , How to reverse the entire list ？

//  Reverse to  a  Is the linked list of the head node 
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 pointer position 
        pre = cur;
        cur = nxt;
    }
    //  Returns the inverted head node 
    return pre;
}

This time, we use the idea of iteration to achieve , It should be easy to understand with animation .

「 Reverse to a Is the linked list of the head node 」 In fact, that is 「 reverse a To null The node between 」, So if you're allowed to 「 reverse a To b The node between 」, Will you ？

Just change the function signature , And put the code above null Change to b that will do ：

/**  Reverse the interval  [a, b)  The elements of , Attention is left closed, right open  */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while  Just change the termination conditions 
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    //  Returns the inverted head node 
    return pre;
}

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

Now we iteratively implement the function of reversing part of the linked list , Next, I'll write it according to the previous logic reverseKGroup Function ：

ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    //  Section  [a, b)  contain  k  Elements to be reversed 
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        //  Insufficient  k  individual , There is no need to reverse ,base case
        if (b == null) return head;
        b = b.next;
    }
    //  Before reversal  k  Elements 
    ListNode newHead = reverse(a, b);
    //  Recursively reverses subsequent linked lists and joins them 
    a.next = reverseKGroup(b, k);
    return newHead;
}

Explain it. for A few lines of code after the loop , Be careful reverse The function is an inverse interval [a, b), So the situation is like this ：

The recursive part is not expanded , This is the result of the recursion of the entire function , It's completely in line with the meaning of the question ：

3、 ... and 、 Finally, say two words

In terms of the amount of reading , The basic data structure related algorithm articles are not many people , I'd like to say that it's going to suffer .

People like to look at dynamic planning issues , Maybe because interviews are very common , But I understand it personally , A lot of algorithmic ideas are derived from data structure . One of the famous names of our official account. ,「 Frame thinking of learning data structure 」 Just mentioned , What moving rules 、 to flash back 、 Divide and conquer algorithm , It's all tree traversal , The structure of tree is not a multi cross linked list ？ You can deal with basic data structures , Solving general algorithmic problems should not be too laborious .

So how to decompose the problem 、 What about recursion ？ This can only be practiced more , Maybe we can write a special article to discuss , This is the end of this article , Hopefully that helped ！

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

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！