Reverse Nodes in k-Group

Description

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.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

Solution(javascript)

// O(n) 记录首节点和尾节点
const reverseKGroup = (head, k) => {
  const reverse = (node) => {
    let count = 1
    let current = node
    let next = null
    let newHead = null

    while (count <= k && current) {
      newHead = current
      const temp = current.next
      current.next = next
      next = current
      current = temp
      count += 1
    }
    node.next = current
    return [newHead, node]
  }
  const getLength = (node) => {
    let length = 0
    let current = node
    while (current) {
      length += 1
      current = current.next
    }
    return length
  }
  const times = Math.floor(getLength(head) / k)
  let newHead = null
  let current = head
  let tail = null
  for (let i = 1; i <= times; i++) {
    const [partHead, partTail] = reverse(current)
    if (!newHead) {
      newHead = partHead
    }
    if (tail) {
      tail.next = partHead
    }
    tail = partTail
    current = partTail.next
  }
  return newHead || head
}