This is the 23rd day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

leetcode Flip linked lists in groups of K

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order.

Advanced:

Can you design an algorithm that only uses constant extra space to solve this problem? You can’t just change the values inside the nodes, you need to actually swap nodes.

Example 1:

Input: head = [1,2,3,4,5], k = 2 output: [2,1,4,3,5]Copy the code

Example 2:

Input: head = [1,2,3,4,5], k = 3 output: [3,2,1,4,5]Copy the code

Example 3:

Input: head = [1,2,3,4,5], k = 1 output: [1,2,3,4,5]Copy the code

Example 4:

Input: head = [1], k = 1 output: [1]Copy the code

Problem solving: Flipping a linked list with k nodes as a group is similar to swapping between two nodes, but there are not fixed 2 nodes, but K nodes, so it cannot be completed by swapping in pairs. Then, the whole linked list can be regarded as a large linked list composed of K nodes. For example, node1->node2->node3->node4->node5 is divided into [node1->node2]->[node3->node4]->[node5] by k nodes, and then the linked list by K nodes is flipped by stack. Specific definition of a temp pointer to the head, by moving the temp Pointers grouped, each move temp k, mobile will be referred to in temp node in the stack, and the k node to remove the stack node joining together behind the result list, when no one grouping k nodes, ends circulation, by the way the rest of the node to take back the result list.

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode reverseNode = new ListNode();
        ListNode pNode = reverseNode;
        Deque<ListNode> deque = new ArrayDeque<ListNode>();

        // Group linked lists by k length
        while (true) {
            boolean isNull = true;
            // The temp pointer traverses the nodes of each group
            ListNode temp = head;
            // Take the nodes of each group and add them to the stack
            for (int i = 0; i < k; i++) {
                // There are no k nodes in this group
                if (isNull = temp == null) {
                    break;
                }
                // Add the temp pointer to the linked list later
                deque.push(temp);
                temp = temp.next;
            }
            // Reconnect it
            if (isNull) {
                pNode.next = head;
                break;
            }
            // Take the stack node and add it to the resulting list in order to reverse each k-length group
            while(! deque.isEmpty()) { pNode.next = deque.pop(); pNode = pNode.next; }// Continue to the next group
            head = temp;
        }
        returnreverseNode.next; }}Copy the code

Or use recursion to find a list of k nodes, flip the list first, connect it to the end of the resulting list, and repeat the rest of the list recursively until there are no k nodes left.

public ListNode reverseKGroup(ListNode head, int k) { ListNode temp = head; For (int I = 0; i < k; i++) { if (temp == null) { return head; } temp = temp.next; ListNode newHead = reverse(head, temp); Head. Next = reverseKGroup(temp, k); reverseKGroup(temp, k); return newHead; } /** * reverse list ** @param head * @param tail * @return reverse list */ private ListNode reverse(ListNode head, ListNode tail) { ListNode pre = null; ListNode next; while (head ! = tail) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }Copy the code