This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Topic describes

Their thinking

  1. First determine whether the length of the incoming list is less than K, if less than K, return the original list.
  2. If the length of the list passed in is greater than or equal to k, proceed.
  3. Initialize two Pointers,prev and cur. Prev is initialized to null, and cur is initialized to head.
  4. The core loop: first saves the next pointer to the current pointer, then advances prev by one, advances cur by one, puts the cur pointer into recursion, and returns prev at the end of all recursions.

AC code

var reverseKGroup = function(head, k) {
  // First check whether the length of the passed list is less than k, if so, return the original list
  let flag = 0;
  let temp = head;
  while (temp) {
    temp = temp.next;
    flag++;
  }
  if (flag < k) {
    return head;
  }
  // Initialize the pointer
  let prev = null;
  let cur = head;
  let n = k;
  while(cur ! =null && n-- > 0) {
    // Save the latter node first
    let next = cur.next;
    // The next field of the cur pointer points to the previous node
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  // Modify the next field of the head pointer to point to the recursive result
  head.next = reverseKGroup(cur,k);
  return prev;
};
Copy the code

Diagram core Idea

The title to reflect

  • In the case of list inversion, we might use three Pointers, so we have to think about that.
  • When a pointer is reversed, it is important to save the next pointer to prevent it from being lost.
  • As you loop, make sure you know where each pointer is at the end of the loop, and what each pointer means. Only when you know this, will you know which pointer to put into the recursion and what the recursion returns.
  • In the list category, reversing the various lists is a common interview question, this question refers to our second thought.

Refer to the link

  • LeetCode antithesis