This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

Leetcode-cn seems to be dead again, use English

The title

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

 

Example 1:

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

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]

 

Constraints:

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

 

Follow-up: Can you solve the problem in O(1) extra memory space?

Their thinking

The linked list is flipped by a group of K nodes.

Scan the Linked List from left to right, dividing the array into segments in units of K and flipping each segment. Given head and tail nodes, how to flip the linked list.

Flipping a list initializes a null previous node (prev) and then traverses the list with the current node (curr) next pointing to the previous node (prev) before changing the current node’s pointing. Use a temporary variable to record the next node of the current node (curr.next). namely

ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp;

For example, flip the entire list 1->2->3->4-> NULL ->4-> 3->2->1-> NULL

Here is the rollover of each group (K nodes),

  1. Group first, using a count variable to record the number of current nodes

  2. Use a start variable to record the node preceding the start node location of the current grouping

  3. Use an end variable to record the last node position to be flipped

  4. Flip a group (k nodes) i.e. (start, end) \ -start and end autistic.

  5. After flipping, start points to the last node in the flipped list (start, end) and returns the start node.

  6. If there is no need to flip, end is moved back one (end=end.next), and count+1 for each move.

As shown in figure 4 and 5: Reverse interval linked list interval (start, end)

For example, head=[1,2,3,4,5,6,7,8] and k = 3

NOTE: A new dummy node may be introduced to a linked list because the head may change. Dummy (List(0)) remains unchanged.

Complexity analysis

  • Time complexity: O(n) - n is number of Linked List
  • Space complexity: O(1)

Critical point analysis

  1. Create a dummy node
  2. Group linked lists in units of K, and record the start and end node positions of each group
  3. Flip each group, changing the starting and ending positions
  4. returndummy.next.

code

/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var reverseKGroup = function(head, k) {
  / / pacesetter
  let dummy = new ListNode()
  dummy.next = head
  let [start, end] = [dummy, dummy.next]
  let count = 0
  while(end) {
    count++
    if (count % k === 0) {
      start = reverseList(start, end.next)
      end = start.next
    } else {
      end = end.next
    }
  }
  return dummy.next

  // reverse the stat -> end list
  function reverseList(start, end) {
    let [pre, cur] = [start, start.next]
    const first = cur
    while(cur ! == end) {let next = cur.next
      cur.next = pre
      pre = cur
      cur = next
    }
    start.next = pre
    first.next = cur
    return first
  }
};
Copy the code

extension

  • It requires a group of K flips from back to front. (ByteDance interview question)

    For example, 1->2->3->4->5->6->7->8, k = 3,

    K equals 3 from the back,

    • 6-7 - > > 8For a group of inverts8 - > 7 - > 6.
    • 3 - > 4 - > 5For a group of inverts5 - > 4 - > 3.
    • 1 - > 2There are only 2 nodes lessk=3One, do not flip.

    Finally return: 1->2->5->4->3->8->7->6

The idea here is similar to flipping k in a group, which can be preprocessed:

  1. Reverse a linked list

  2. Flip the flipped list from front to back in groups of K.

  3. Reverse the linked list obtained in Step 2.

Example: 1->2->3->4->5->6->7->8, k = 3

  1. Flip the list to get: 8->7->6->5->4->3->2->1

  2. Flip k as a group: 6->7->8->3->4->5->2->1

  3. Flip steps #2 linked list: 1->2->5->4->3->8->7->6

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front-end brush problem” No.25