Today, I will brush problem 25 in LeetCode, and record the idea of brush problem, so that I can refer back to it in the future. (It’s easy to forget if you don’t write for a week, so practice more.)

There are three possible solutions to this problem:

  1. Using the idea of stack first out, when the linked list elements k groups into the stack, and then out. (The disadvantage is that the time complexity is high, the stack and stack have to traverse the linked list, not recommended, understand the idea can be).
  2. Recursion: perform recursion in a group of K, please refer to the diagram below for specific ideas.
  3. Iteration: same as above, refer to the diagram below.

Without further ado, first the code:

With the help of a stack

Deque<ListNode> stack = new LinkedList<>(); ListNode dummy = new ListNode(0); ListNode p = dummy; ListNode p = dummy; while (true) { int count = 0; ListNode temp = head; ListNode temp = head; ListNode temp = head; ListNode temp = head; ListNode temp = head; // add k to stack while (temp! = null && count < k) { stack.push(temp); temp = temp.next; count++; } // If (count! = k) { p.next = head; break; } while (! stack.isEmpty()) { p.next = stack.pop(); p = p.next; } // Head = temp; } return dummy.next;Copy the code

There is nothing to be said for this idea: use a pointer p to follow the stack in turn and return dummy. Next when there are fewer than k.

Look at a few key ideas of linked list code

Here are a few things to emphasize when coding linked lists:

1, linked lists often have the following code, beginners will look very strange, I also confused for a long time at the beginning of learning:

        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
Copy the code

Dummy p = dummy p = dummy P = dummy P = dummy Why not just use dummy?

Dummy node (p=p) dummy node (p=p) dummy node (p=p) dummy node (p=p) Dummy needs to create a new helper to do this for him, namely P.

This logic will be used a lot in linked list code, so it won’t feel like a fog when you look at the code.

2, linked lists often have the following xx.next flying around, it can be difficult to understand.

head.next=next.next.next;
next.next=head;
Copy the code

When xx. Next is to the left of the expression, it has only one meaning. The next node of XX points to the right of the expression.

As the head. The next = next. Next; Head points to the next node of next. This way you can comb through the previously confusing code and make it much clearer. I think a lot more clearly anyway.

3, Once a.ext =B, the position pointer to A is broken and now points to B. Note in advance if you need to use the previous a.ext node later. So in linked lists you’ll often see code like this:

                ListNode next = tail.next.next;
                tail.next.next = prev.next;
                prev.next = tail.next;
                tail.next = next;
Copy the code

Tail.next. Next is broken in line 2 and needed in line 4, so we save tail.next.

At first glance, the third point is similar to the first point, but there are subtle differences. One is a record where the pointer moves, and the other is a record where the pointer breaks.

recursive

        int count = 0;
        ListNode curr = head;
        while(curr ! =null && count < k) {
            curr = curr.next;
            count++;
        }

        if (count == k) {
            curr = reverseKGroup(curr, k);
            while (count-- > 0) {
                ListNode temp = head.next;
                head.next = curr;
                curr = head;
                head = temp;
            }
            head = curr;
        }

        return head;
Copy the code

The code is actually pretty clear, so let’s go through it bit by bit.

        int count = 0;
        ListNode curr = head;
        while(curr ! =null && count < k) {
            curr = curr.next;
            count++;
        }
Copy the code

The main purpose of this code is to group k nodes, where ListNode curr=head; Using my basic point above, since the original head position is not found if you move it back directly with head, you need a helper, Curr, to help it do this.

And then if you look down, if you have k nodes, you flip k nodes, otherwise you go straight back.

curr = reverseKGroup(curr, k); So this is a recursive call, but the point here is when you’re looking at the code that’s related to recursion don’t force human recursion, you’re going to be miserable, and you’re going to confuse yourself, because we’re not machines. All we need to know is that the result of this code is that the curr processed by reverseKGroup(curr, k) is a set of k, and all we need to do now is flip the k elements in front of the curr so that we can assemble them.

The following code does just that:

			while (count-- > 0) {
                ListNode temp = head.next;
                head.next = curr;
                curr = head;
                head = temp;
            }
            head = curr;
Copy the code

This is not so easy to understand, in this case usually draw a picture, the problem is solved

For example, head = [1,2,3,4,5], k = 3. The drawing may be a little ugly, but it might help you.

K is equal to 3, so it’s only going to loop three times, and when it’s done, the curr is at the head, and the head is at temp, so I need to put head=curr. Finally, return to head.

The iteration

        int n = 0;
// Count the length of the linked list
        for(ListNode i = head; i ! =null; n++, i = i.next);

        ListNode dmy = new ListNode(0);
        dmy.next = head;
        for(ListNode prev = dmy, tail = head; n >= k; n -= k) {
            for (int i = 1; i < k; i++) {
                ListNode next = tail.next.next;
                tail.next.next = prev.next;
                prev.next = tail.next;
                tail.next = next;
            }

            prev = tail;
            tail = tail.next;
        }
        return dmy.next;
Copy the code

Iterative code may be a little round, xx.Next-next this style, do not have fear, after reading the idea is still very clear.

The first two lines of code use n to count the list length. Among them, the writing method of traversing the linked list is still very novel and worth learning from.

Dummy = prev; head = tail; dummy = prev; head = tail

for(ListNode prev = dmy, tail = head; n >= k; N -= k) this code flips the list in groups of k.

For (int I = 1; i < k; I++) so I’m starting at 1 instead of 0, so it feels like one less loop. The way I think about it is, when you have k numbers, when you actually flip it you only flip it k minus 1 times, and there’s no problem with 1.

Please refer to the picture below for a concrete loop idea. It’s a little messy. I’m sure you can understand it

Prev and tail are adjacent to each other. Tail.next. Next =prev.next Refers to the pointer from tail to prev’s next node.

Next =tail. Next means that prev points to the next node of tail.

Tail.next =next refers to the position where tail was located before tail.next-next. Next is not used directly because the pointer is broken now, so we use the saved next.

After k flips, prev and tail are reassigned for the next round.

The final return is the original head position, but since the head has been moved to some unknown location, dummy. Next is the original head position.

Write in the last

These three solutions mainly master recursion and iteration, stack is actually meaningless, time complexity is too high, it is difficult to use, except for some special scenarios.

In fact, iteration and recursion are very round, often appear today will write, after a week and a little not, so read and write more, no way, come on!