“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Flip linked lists in groups of 52. K

The title

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:

Input: head = [1,2,3,4,5], k = 2 output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3 output: [3,2,1,4,5]

Example 3:

Input: head = [1,2,3,4,5], k = 1 output: [1,2,3,4,5]

Example 4:

Input: head = [1], k = 1 output: [1]

Tip:

The number of nodes in the list is within the range sz 1 <= sz <= 5000 0 <= node. val <= 1000 1 <= k <= sz

Advancements: Can you design an algorithm that only uses constant extra space to solve this problem?

You can’t just change the values inside the nodes, you need to actually swap nodes.

Answer key

Ask questions

  • How do I group inversion and keep the linked list nodes from being lost during inversion?

Analysis of the iteration

  • Looking at the reversed linked list from Example 1, you want to add eachkA group of nodes is reversed.
  • So let’s definetempVirtual node, willtemp.nextPointing to the head node
  • defineprePoint to thetemp, define pointertailPoint to thepreThe node pointed to.

  • willtailThe pointer moves backwards at the same time until it finds itkA node

  • To define aprevPoint to thetailThe next node of the node pointed to.
  • definePPoints tohead.
  • Define a pointernextPoint to thePThe next node of the node pointed to.

  • Point to the node to which the P pointer pointsprevThe node to which the pointer points.

  • willprevMove to thePThe position of the pointer.
  • willPPointer moved tonextThe position of the pointer.
  • nextMove back one.

  • Repeat the preceding steps whenperA pointer totailWhen the pointer points to the same node, the list inversion of the entire K nodes is completed.

  • willpreThe node to which the pointer points pointstailThe node to which the pointer points.

  • Tidy it up

  • prePointer moved toheadThe position of the pointer.

  • headPointer moved toprePointer to the next node of the node
  • tailPoint to theprePointer to node

  • thentailThe node moves againkStep, whentailThe node tonull, prove that the following nodes are insufficientK, the linked list is returned.

  • If I don’t point tonull, continue to repeat the above operations until pointing tonullSo far.

Code implementation

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let temp = new ListNode(0,head)
    let p = temp
    do{
        p.next = reverse(p.next,k)
        for(let i = 0; i < k && p; i++) p = p.next
        if(p == null) break
    }while(true)
    return temp.next
};

var reverse = function(head,n){
    let pre = head
    let cur = head
    let cnt =  n
    while(--n && pre) pre = pre.next
    if(pre == null) return head
    pre = null
    while(cnt--){
        [cur.next,pre,cur] = [pre,cur,cur.next]
        // let next = cur.next
        // cur.next = pre
        // pre = cur
        // cur = next
    }
    head.next = cur
    return pre
}
Copy the code