[luffy]_K flip linked list in a group

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