LeetCode algorithm learning — list –K groups to flip the list

Hello everyone today to share the next LeetCode difficult difficulty problem [K a group of reverse linked list](leetcode-cn.com/problems/li…)

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

I give you a list, and I flip it every k nodes, and I ask you to return the 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, leave the last remaining nodes in their original order.

Example 1 (image reprinted by LeetCode)

Example 2 (image reprinted by LeetCode)

Example 1 Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4, 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 = 1Copy the code

Analysis of the

K is a positive integer

2. If the length of the list is not an integer multiple of K, retain the order of the remaining nodes

Dummy = dummy = dummy = dummy = dummy = dummy

4. Use what we learned about flipping lists

solution

1. The iteration

2. Recursively

Solution 1: iteration

Code reference leetcode-cn.com/problems/re…

Train of thought1.Let's start by grouping the list into k elements2.Move the pointer pre to the last node of the group head and the pointer end to the end of the group3.Flip the elements inside the group4.Move pre to the node above the head of the next group and end to the end of the next group */var reverseKGroup = function (head, k) {
  let dummy = new ListNode(0);
  dummy.next = head;
  // Set two Pointers, pre and end
  let pre = dummy;
  let end = dummy;

  while(end.next ! = =null) {
    // Move end to the end of the group
    end = reachKNode(end, k);
    // If there are any cases where end is equal to undefined, that means there are not enough nodes left
    // Close the loop directly
    if(! end)break;

    // Determine the start node in the group and the start node for the next group
    const start = pre.next;
    const next = end.next;
    // Break the end of the last node in the group to easily flip the list
    end.next = null;
    // Start becomes the end
    pre.next = reverse(start);
    // Make start point to the node at the start of the next group
    start.next = next;

    // Put the pre and end Pointers to the last node of the flipped list,
    // Prepare for the next iteration
    pre = start;
    end = pre;
  }

  return dummy.next;

  // End at the end of the group
  function reachKNode(node, k) {
    while (k > 0) {
      // Return false if one is equal to zero
      if(! node) {return false;
      }
      node = node.next;
      k--;
    }

    return node;
  }

    // Reverse the list iteration method
    function reverse(node) {
      let pre = null,
        cur = node;
      while (cur) {
        let n = cur.next;
        cur.next = pre;

        // Move the pointer
        pre = cur;
        cur = n;
      }
      returnpre; }};Copy the code

Solution 2: recursion

The idea is the same as iteration except that the reverse method is solved recursivelyvar reverseKGroup = function (head, k) {
  let dummy = new ListNode(0);
  dummy.next = head;
  // Set two Pointers, pre and end
  let pre = dummy;
  let end = dummy;

  while(end.next ! = =null) {
    // Move end to the end of the group
    end = reachKNode(end, k);
    // If there are any cases where end is equal to undefined, that means there are not enough nodes left
    // Close the loop directly
    if(! end)break;

    // Determine the start node in the group and the start node for the next group
    const start = pre.next;
    const next = end.next;
    // Break the end of the last node in the group to easily flip the list
    end.next = null;
    // Start becomes the end
    pre.next = reverse(start);
    // Make start point to the node at the start of the next group
    start.next = next;

    // Put the pre and end Pointers to the last node of the flipped list,
    // Prepare for the next iteration
    pre = start;
    end = pre;
  }

  return dummy.next;

  // End at the end of the group
  function reachKNode(node, k) {
    while (k > 0) {
      // Return false if one is equal to zero
      if(! node) {return false;
      }
      node = node.next;
      k--;
    }

    return node;
  }

  / / the recursive method
  function reverse(node) {
    if(! node || ! node.next) {return node;
    }

    const endNode = reverse(node.next);
    node.next.next = node;
    node.next = null;
    returnendNode; }};Copy the code

conclusion

This question is a comprehensive review of the previous pairwise exchange and flip lists. If you are interested, check out the pairwise exchange and flip lists shared in my column

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]