Last time we looked at the second brother of single-linked list inversion — swapping nodes in pairs. Today let’s analyze its big brother: “a group of K flipped linked lists”.

The description is as follows.

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.

Example:

Here’s a list: 1->2->3->4->5

When k = 2, it should return: 2->1->4->3->5

When k = 3, it should return: 3->2->1->4->5

If the first to do a group of K flip linked list this problem, the difficulty is relatively large, if the front of its two younger brother foreshadowing, then the problem is natural, the answer of the first two questions combined is the answer of the problem. This problem, like its two Cousins, can be solved by iteration and recursion.

Method 1: three-pointer iteration

With the basis of the double pointer iterative method of single linked list inversion, it is relatively easy to solve its second brother. One cannot make bricks without straw. In the title, K nodes are flipped in a group, so there must be K nodes first. It is the same as “swapping nodes in a linked list in pairs”, the first judgment is enough for K nodes before continuing to swap, and the cycle continues only when there are enough remaining nodes. We can use two variables, left and right, to represent the start and end nodes in the list that we are currently flipping.

As shown in the figure above, Pointers L and R represent the start and end nodes of a list to be flipped. To find the KTH node in a list, we can write a method that returns the pointer to the KTH node if the length of the remaining list is K, or null if the length of the remaining list is K:

private ListNode findKthNode(ListNode p, int k) {
  int curCount = 0;
  while (curCount < k - 1&& p ! =null) {
    p = p.next;
    curCount++;
  }
  return (curCount == k - 1)? p :null;
}
Copy the code

The only difference is that the end pointer is the tail pointer, and here the end pointer is specified — the KTH node of each segment of the list. There are two kinds of iteration and recursion. In order to keep the consistency of the method, the iterative method is also used here. The implementation code is as follows:

 private void reverseRange(ListNode left, ListNode right) {
    if (left == right) {
      return;
    }
    ListNode exit = right.next;
    ListNode cur = left, pre = null;
    while (cur != exit) {
      ListNode next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
}
Copy the code

At the same time, consider the following scenario, the K nodes in the first segment have been flipped, and now it is the turn of the second segment to flip. After that, the pre needs to point to the R node, so it also needs to record the precursor node for each round of swapping. In this example, the precursor node is node 1.

The overall code implementation is as follows:

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode pre = null, left = head, right = findKthNode(head, k);
    if (right == null) {
      return head;
    }
    ListNode ans = right;
    while(left ! =null&& right ! =null) {
      ListNode next = right.next;
      reverseRange(left, right);
      left.next = next;
      if(pre ! =null) {
        pre.next = right;
      }
      pre = left;
      left = next;
      right = findKthNode(next, k);
    }
    return ans;
  }

  private void reverseRange(ListNode left, ListNode right) {
    if (left == right) {
      return;
    }
    ListNode exit = right.next;
    ListNode cur = left, pre = null;
    while (cur != exit) {
      ListNode next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
  }

  private ListNode findKthNode(ListNode p, int k) {
    int curCount = 0;
    while (curCount < k - 1&& p ! =null) {
      p = p.next;
      curCount++;
    }
    return (curCount == k - 1)? p :null; }}Copy the code

Looking at the code above, it has the same structure as swapping nodes in a linked list in pairs. The following figure shows the code comparison. It can be seen that the code patterns at 1 and 2 are the same. “nodes swapping linked lists in pairs” is a special case of “a group of K flipping linked lists” when K=2.

Complexity analysis

  • Time complexity:O(n).
  • Space complexity:O(1).

Method two: recursion

Recursion is also a combination of its two younger siblings.

The recursion of a flip in a segment is the same as that of a “flip in a single list”. The only difference is that the recursion exit condition is different. The recursion exit condition of a flip in a segment is that the left pointer meets the right pointer, while the recursion exit condition of a single list inversion is that the current node is empty or the current node is already a tail node.

Again, this is written the same way as “nodes in a pairwise switched list”, which is a special case of “a group of K flipped lists” when K is 2.

The code is as follows:

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    ListNode left = head, right = findKthNode(head, k);
    if (right == null) {
      return left;
    }
    ListNode next = reverseKGroup(right.next, k);
    reverseRange(left, right);
    left.next = next;
    return right;
  }

  private void reverseRange(ListNode left, ListNode right) {
    if (left == right) {
      return;
    }
    reverseRange(left.next, right);
    left.next.next = left;
    left.next = null;
  }

  private ListNode findKthNode(ListNode p, int k) {
    int curCount = 0;
    while (curCount < k - 1&& p ! =null) {
      p = p.next;
      curCount++;
    }
    return (curCount == k - 1)? p :null; }}Copy the code

Complexity analysis

  • Time complexity:O(n).
  • Space complexity:O(n), recursion is used, the stack depth of recursion isn.