• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

preface

This is a seemingly simple, but is the details of the dead topic.

Topic links: a group of K flip linked lists

Train of thought

The problem would have been a simple one if it had been done in stacks or recursions, but the point is that the problem requires extra space at a constant level.

1. First get the length of the list

2. In the case of K, if K == 1 or K > length, obviously you don’t need to flip it

3. Define a cur,last to the current node,last to the previous node, pref to the last node in the previous k-chain, and startNode to the first node in the order of each k-chain.

4. When the current node is not the last node in the K chain, the next of the current node points to the last node to realize the flipping in the K chain

5. When the current node is the last node in the K chain

   (1) Next of the current node points to last node. This node is also the head of the k chain, so the last node in the last k chain pref.next = cur; If pref==null. The current node is the Head node in the first K-chain.

   (2) Update pref to the last node in the K chain, namely startNode.

   (3) When the head node of the next K chain is not determined, pref.next points to the next first node. The purpose is to prevent k cases that do not meet the following conditions, resulting in no prefix in the header

   (4)startNode updates the first node pointing to the next unflipped K chain.

code

public ListNode reverseKGroup(ListNode head, int k) {
        ListNode pref = null;
        ListNode cur,last, startNode,t;
        int length = getLength(head);
        int endIndex = length - length%k -1;
        if (k == 1 || k > length) return head;
        int i = 0;
        cur = head;
        startNode = head;
        last = null;
        while(cur ! =null) {
            if (i > endIndex){
                break;
            }
            At the end of / /
            if (i % k == k - 1) {
                t = cur.next;
                if (pref == null) {// indicates the header
                    head = cur;// Currently as head
                } else {
                    pref.next = cur;
                }
                cur.next = last;// Visit last time
                cur = t;
                pref = startNode;// The start node of the previous round, which is also the end of the previous round, becomes the prefix of the next k-long list
                pref.next = cur;// Point it to the head of the next k-list of changes. The purpose is to prevent the following k cases that do not meet the prefix of the head
                startNode = cur;// a new round of k
            } else {
                t = cur.next;
                cur.next = last;
                last = cur;
                cur = t;
            }
            i++;
        }
        return head;
}
public int getLength(ListNode head){
    int size = 0 ;
    while(head! =null){
        head= head.next;
        size++;
    }
    return size;
}
Copy the code