I participated in the 12th day of The November Gwen Challenge, the event details: 2021 last Gwen Challenge

  1. First, group linked lists
  2. Flip the linked list for each group
  3. If the number of nodes is less than K, connect the nodes again.

To the problem solving
  1. You need to create a temporary node for the linked listfakePoint to thehead, define two variablespre.tailAll pointing to temporary nodesfakeTo definenextintailThe back of thetailMove backwards according to K, and then flip. The flip is done, will bepre``nextThe connection.
  2. After completing 1, willpre head tail nextI’m going to flip it backwards by K. Connect pre Next
  3. Repeat step 2 untiltail.nextThere is no
function myReverse(head, tail) {
  let prev = tail.next;
  let cur = head;
  while(prev ! = tail) {const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  // return a new header and a new tail
  return [tail, head];
}
var reverseKGroup = function (head, k) {
  // Virtual head node
  let fake = {
      next: head
  }
 
  let pre = fake; / / define the pre
  while (head) {
    let tail = pre;
    for (let i = 0; i < k; i++) {
      // Move tail back K times
      tail = tail.next;
      // If there is no jump
      if(! tail) {returnfake.next; }}const next = tail.next;
    [head, tail] = myReverse(head, tail);
    // Identify the head of the next group

    // connect the header and tail
    pre.next = head;
    tail.next = next;

    // Determine the start and end of the next group
    head = tail.next;
    pre = tail;
  }
  return fake.next;
};
Copy the code

The flipping function used is the same as before to flip the whole list, followed by the records of Pre Next. After the flipping, pre Next will be used to join together. If tail.next exists, the flipping of the next group will continue, otherwise it will end and return hair.next.

conclusion

Algorithm needs is a kind of thinking mode, when we need to think of a certain level, that is to say, we have seen enough algorithm problems, see the problem can think of the corresponding ideas, this time can calmly deal with. So in the initial algorithm is the most difficult time, as long as we insist to break through one by one, I believe there will be a day to tear it by hand.