Subject to introduce

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 1

Enter: head = [1.2.3.4.5], k = 2Output:2.1.4.3.5]
Copy the code

Example 2

Enter: head = [1.2.3.4.5], k = 3Output:3.2.1.4.5]
Copy the code

Example 3

Enter: head = [1.2.3.4.5], k = 1Output:1.2.3.4.5]
Copy the code

Example 4

Enter: head = [1], k = 1Output:1]
Copy the code

Tip:

  • The number of nodes in the list is in the rangesz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

Leetcode -25 K sets of flipped list B station videos

Their thinking

1. If the value of k is 1, you do not need to perform the reversal and can directly return the head node 2. Define a virtual head node whose next node points to the head node. 3. Define a pre pointer to the virtual head node, and define s and E Pointers to the head node to indicate the start and end positions of the list to be reversed respectively. If e points to an empty node, it indicates that the number of nodes in the current linked list is insufficient for flipping, and the head node of the linked list is directly returned to end the whole process 6. Otherwise flip the list between S and E and insert it after the last node in the flipped list 7. Pre points to the node where S is, and S and E point to the next node of S, 8. Repeat the process 4-7 until the length of the list to be flipped is less than k

The problem solving code

var reverseKGroup = function(head, k) {
    if (k === 1) return head
    const newNode = new ListNode(-1, head)
    let pre = newNode, n = k, s = e = head
    while (s) {
        while (--n && e) {
            e = e.next
        }
        if(! e)return newNode.next
        pre.next = reverse(s, k)
        pre = s
        s = e = s.next
        n = k
    }
    return newNode.next
};

var reverse = function(head, k) {
    let cur = head, next = head.next
    while (--k) {
        head.next = next.next
        next.next = cur
        cur = next
        next = head.next
    }
    return cur
}
Copy the code

For example, if you want to make a list of happy numbers, you can find a list of happy numbers. If you want to make a list of happy numbers, you can find a list of happy numbers