“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Topic:

25. Flip linked lists in groups of K

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.

Advanced:

  • 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.

 

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: head = [1], k = 1 output: [1]Copy the code

Tip:

  • The number of nodes in the list is in the rangesz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

Ideas:

  1. Calculate the total length of the listtotal;
  2. Figure out how many flips it takes to do the listcount = Math.floor(total / k);
  3. performcountAfter each flip, it is joined to the sorted linked list
  4. Lack of restkTo add to the already organized list

Implementation:

/** * 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}* /
function reverseKGroup(head, k) {
  let total = 0;
  let cur = head;
  // Count the total length of the linked list
  while (cur) {
    cur = cur.next;
    total++;
  }

  // Calculate the number of flips required
  const count = Math.floor(total / k);
  let result, temp;

  // iterate over to do the flip
  for (let i = 0; i < count; i++) {
    let { prev, next } = reverseNode(head, k);
    head = next;

    // after the first flip as the head node
    if (i === 0) {
      result = prev;
      temp = result;
    } else {
      // The linked data goes to the end, waiting for the next set of flipped nodes
      while(temp.next) { temp = temp.next; } temp.next = prev; }}// The linked data goes to the end, waiting for the next set of flipped nodes
  while (temp.next) {
    temp = temp.next;
  }
  temp.next = head;
  return result;
}

// Invert the first K elements of the list
function reverseNode(cur, k) {
  let prev = null;
  let next = null;

  while (k) {
    next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
    k--;
  }

  return {
    prev,
    next,
  };
}

Copy the code

To optimize the

A review of the above code shows that there is a lot of redundancy in the code. For example, every time you get a sorted list, you have to do k rounds of backward evaluation of the list. And you have to start with a total count, which is the equivalent of traversing the list three times. Therefore, the following adjustments were made:

  1. Cancel the first firsttotalChange the operation to useindexCount before each flip, satisfyindex === kPerform reverse
  2. Instead of returning the entire list at the end of each flip, only the head and tail nodes are returned
  3. Put the nodes that have been sorted outnextPoints to the head node after the current flip, and the tail node after the current flip points to the head node of the next round

Optimize the code

/** * 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}* /
function reverseKGroup(head, k) {
  // Do not rotate a group
  if (k === 1) {
    return head;
  }
  // Create an empty node so that you don't have to check the head node for each loop later. The result returns result.next
  let result = { val: 0.next: null };
  let cur = head;

  let prev = result; // Cache the last trailing node
  
  while (cur) {
    let index = 1;
    let temp = cur;
    while (index < k && temp.next) {
      temp = temp.next;
      index++;
    }

    const next = temp && temp.next;

    // If k units are satisfied, do rotation operation. If not, the game ends
    if (index === k) {
      let { first, last } = reverseNode(cur, k);
      prev.next = first; // The last node of the previous round points to the first node of the current round
      prev = last;
    } else {
      prev.next = cur;
    }

    cur = next;
  }

  return result.next;
}

// Invert the first K elements of the list
function reverseNode(cur, k) {
  let last = cur; // The current head node is flipped to become the tail node

  let prev = null;
  let next = null;

  while (k) {
    next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
    k--;
  }

  return {
    first: prev,
    last,
  };
}

Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.