Flip linked lists in groups of K

Topic describes

Given a linked list, a group of k nodes is flipped, please return the flipped linked list; K is a positive integer not greater than the length of the list; If the total number of nodes is not an integer multiple of k, leave the last remaining node as it is

The sample

The head = [1, 2, 3, 4, 5]

k = 1

// No need to flipOutput:1.2.3.4.5]
Copy the code

k = 2

// 1,2 group flip 2,1
// 3,4 do the flip 4,3
// The last remaining 5 is left unchangedOutput:2.1.4.3.5]
Copy the code

k = 3

// 1,2,3 group flip 3,2,1
// The last remaining 4 and 5 remain unchangedOutput:3.2.1.4.5]
Copy the code

Their thinking

Take head = [1,2,3,4,5] k=2

  • First of all, there must be groups

    • So we need to define the current group head and tail

    • // head points to the head node
// tail = k
head   tail
 1  ->  2  ->  3  ->  4  ->  5
Copy the code

    • And then we just flip the sublist

    • head   tail
 2  ->  1  ?  3  ->  4  ->  5
Copy the code

    • But here’s a problem

    • When the sublist flips, 2 must point to 1, but 1 must not point to 3, because 2 points to 3

    • 1, 3 belong to two groups; And the current group is not communicating with the next group at all

    • So there’s a question mark there. If you don’t do this, there will be a problem with the connection

  • So we need to store the next node at the end of the original group, next, which is 3, before flipping the group

  • When the group flip is complete, point the new tail node to next

    • head   tail   next
 2  ->  1  ->  3  ->  4  ->  5
Copy the code

  • So when you finish the first group, keep going

    •               head   tail   next
 2  ->  1  ->  3  ->  4  ->  5

// After the flip
             head   tail   next
 2  ->  1  ?  4  ->  3  ->  5
Copy the code

    • Here’s another problem, and the problem is similar to the one above.

    • 4, 3 after flipping; The relationship between 1 and 4 is messed up again

  • We need to link the flipped head to the tail of the previous list

  • Then we can sum up as follows:

    • When the grouping is complete, we need to point the new tail node tail to next of the original list

    • When the grouping is complete, we need to point the new head node head to the tail of the previous grouping

  • But! We find that the previous group of the first group is NULL

    • We can of course treat the first group specially, but in order to keep the logic uniform

    • Unification refers to the implementation of the two items summarized above for each group completed. So it’s pretty clear what the list is pointing to.

    • So let’s add a new node hair in front of the head, hair can be defined as any value, and then discard it

    • Hair prev head tail next arbitrary value ->1  ->  2  ->  3  ->  4  ->  5
Copy the code

    • After hari was introduced, it changed a little bit, rearranging the meaning of variables

    • hair.next = head   
// Finally we just return hair.next

head // The starting point of the sublist
tail = prev + k // The end of the child list
prev Prev records the end of the last node
next // The next head node of the child list

Copy the code

  • After the sublist is flipped, we make corrections for the head and tail nodes

    • prev.next = head
tail.next = next 
Copy the code

  • And then you go down

    • 
/ / the initialHair Prev arbitrary value ->2  ->  1  ->  3  ->  4  ->  5

// The first groupHair prev head tail next arbitrary value ->2  ->  1  ->  3  ->  4  ->  5


// The second groupHair prev head tail next arbitrary value ->2  ->  1  ->  4  ->  3  ->  5


// The third groupHair prev head tail next arbitrary value ->2  ->  1  ->  3  ->  4  ->  5

Copy the code

    • At this point, it is clear that the tail node has been terminated by null

code

// Reverse the sublist
const myReverse = (head, tail) = > {
  let prev = tail.next;
  let p = head;
  while(prev ! == tail) {const nex = p.next;
    p.next = prev;
    prev = p;
    p = nex;
  }
  return [tail, head];
};
var reverseKGroup = function (head, k) {
  // Define the temporary node hair to point to head
  const hair = new ListNode(0);
  hair.next = head;

  // The end of the last group
  let pre = hair;

  // If the list still has a value
  while (head) {
    // The end of the current group starts at the end of the previous group
    // Then next * k of the last group can locate the new tail
    let tail = pre;
    // Check whether the remaining length is greater than or equal to k
    for (let i = 0; i < k; ++i) {
      tail = tail.next;
      // The total nodes are not multiples of k, and the last remaining nodes need not be processed
      if(! tail) {returnhair.next; }}// Records the next node of the current node
    const next = tail.next;
    // Flips the nodes currently grouped
    [head, tail] = myReverse(head, tail);
    // join the child list back to the original list
    pre.next = head;
    tail.next = next;
    // The location of the next grouping
    pre = tail;
    head = tail.next;
  }
  // Discard hair and return
  return hair.next;
};


Copy the code