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:

  • Here’s a list: 1->2->3->4->5
  • When k = 2, it should return: 2->1->4->3->5
  • When k = 3, it should return: 3->2->1->4->5

Description:

Your algorithm can only use extra space of constants. You can’t just change the values inside the nodes, you need to actually swap nodes.

Recursive thinking

Recursive three cores

  • The return value
  • Call the unit
  • Termination conditions

Apply to the question

  • Return value: flipped linked list
  • Call unit: head and end end flip all Pointers head join flipped linked list
  • Terminating conditions: The remaining length is not an integer multiple of k (the current length is less than k) and head is empty

How to solve the problem

  • List flipping and recursion algorithms
  • First determine whether the length of the incoming list is greater than or equal to k, if not, return the original list
  • When the first condition is met, three Pointers prev, curr and next represent the previous pointer, the current pointer and the next pointer respectively.
    • First, save the next node pointed to by curr to next.
    • The next curr node points to prev.
    • 3. Move the curR and prev Pointers back one step.
    • Fourth step, repeat the previous three steps until the k cycle ends;
  • Finally, we can find that prev is always the head of the list passed in, curr points to the next part to be processed, and head is the end of the list.
  • The curr is the head of a new set of lists to be processed, and the incoming head points to the result of the recursive processing and joins the processed lists.

The problem solving source

/** * 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}* /
/* Recursion: 1. Return value: flipped list 2. Call unit: head and end End Termination conditions: The remaining length is not an integer multiple of k and head is empty */
var reverseKGroup = function(head, k) {
    if(head == null) {return head;
    }
    // Measure the length of the current list
    var nextNode = head.next;
    var pre = head;
    var length = 1;
    for(var i = 0; ; i++){
        if(nextNode == null) {break;
        }
        length++;
        pre = nextNode;
        nextNode = nextNode.next;
    }
    if(length < k){
        return head;
    }

    //end reverses all Pointers
    var curr = head;
    var prev = null;
    var n = k;
    while(curr ! = =null && n-- > 0) {
        var nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }
    
    //head joins the flipped list
    head.next = reverseKGroup(curr,k);
    return prev;
};
Copy the code

conclusion

  • Flip the idea code
    var curr = head;
    var prev = null;
    var n = k;
    while(curr ! = =null && n-- > 0) {
        var nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
 }
Copy the code