Topic describes

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.

Analysis of the

Input: list head node head, packet length K Output: list head node flipped

Their thinking

Do you consider all the details of a linked list operation? Do you consider all the details of a linked list operation?

We’re going to look at specific knowledge points in the process of solving problems.

Let’s talk about the idea first. Since there are k nodes in a group, we can definitely put each K node together as a group of flipped nodes, and then use the head of each group as the node to start the flipped.

So before we start flipping, we need to see if the number of nodes to be flipped is enough for k. If not, we won’t flip. This must be a break while loop ♻️ in the code.

So that’s the whole idea, and after analyzing the whole idea, we can say, how do we flip it?

For example, if we want to flip two nodes as shown in the picture, obviously, we need to pay attention to the node before and after ⚠️ as well as a flip list method. However, we need to take into account the fact that 💭 has only one node, which is what all linked list problems need to be concerned about.

If the list length is 1, we can use a dummyHead, so that we do not need to judge whether the head is 1 or not

So let’s focus on the flip, the flip code can be written as a template, every time we encounter the flip list problem, we can use a fixed routine.

Set a precursor node pre, cur, pre = null.

For example, I want to flip the following linked list, k = 2:

So if I’m going to flip 3 and 4, I’m actually going to flip 4nextIt points to 3 and 3nextTo point to3And then move the entire interval to be operated back by one, i.epre = 4.cur = cur.next

So obviously the preceding node of 3 is null, which is the initial value of pre.

We’re going to code the flip down

function reverse(head) {
        // Set the precursor node to null and the current node cur to head
        let cur = head,
          pre = null;

        // Start the rollover process
        // While loop once, so next of the node that cur points to, we change it to point
        // pre
        // So at the end of each while loop, cur is told to take a step forward and continue to change the next of the following nodes
        // until cur points to null
        while (cur) {
          const tmp = cur.next

          cur.next = pre
          pre = cur
          cur = tmp
        }

        return pre
      }

Copy the code

So let’s think about the first and second nodes.

After the specified interval is flipped, we can see that cur is the first node after the interval, and we should have the unflipped head.next point to this node.

After the flip is complete, we also need to return the new head and have the next pointer of the flipped list precursor point to it.

And finally, let’s think about whether we have k nodes left before we flip.

Let’s look at the complete code:

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var reverseKGroup = function (head, k) {
  if(! head)return null;
  const dummyHead = new ListNode(null, head);
  let pre = dummyHead;

  do {
      // Keep flipping the list
    pre.next = reverseList(pre.next, k);

// Until there are less than k nodes left, this needs to be checked after each flip, and before the flip
    for (let i = 0; i < k; i++) {
    // If there are k, move the pre backwards until you find the next flipped head
      pre = pre && pre.next;
    }

    if(! pre)break;
  } while (true);

// Flip the node's code
  function reverseList(head, k) {
    let pre = head,
      cur = head,
      count = k;

    // Check if remaining nodes serves k, including cur
    while (--count) {
      pre = pre && pre.next;
    }
    if(! pre)return head;

    pre = null;
    while (k--) {
      const tmp = cur.next;

      cur.next = pre;
      pre = cur;
      cur = tmp;
    }
    
    // point to the successor node
    head.next = cur;

    return pre;
  }

// Return next to dummyHead, this is to handle the case where the original head node was processed, conveniently ~
  return dummyHead.next;
};


Copy the code