25. Reverse Nodes in k-Group

Description

Formatted question description: https://leetcode.ca/all/25.html

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

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

Constraints:

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

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

Algorithm

To reverse a linked list in groups of size k, the process involves dividing the original linked list into several segments, each consisting of k nodes, and then individually reversing each segment. This operation necessitates two distinct functions: one for segmenting and another for reversing.

Consider the linked list 1->2->3->4->5 as an example. A common practice in linked list manipulations is to prepend a dummy node to the list. This is because the head of the list might change during the reversal process. The introduction of a dummy node ensures the head’s position is consistently trackable. Consequently, after adding a dummy node, the linked list becomes -1->1->2->3->4->5.

To reverse a group of nodes, for instance, nodes 1, 2, and 3 when k is 3, we employ two pointers: pre and next. The pre pointer indicates the node immediately preceding the group to be reversed, while next points to the node following the group. Post-reversal, the pre pointer advances to mark the new starting position for the next group reversal.

During each iteration for swapping a k-group, prev remains stationary, anchoring the start of the group being reversed, whereas current begins at node ‘1’ and moves through the group. Notably, for the duration of a single batch swap within the while (kcopy > 0) loop, prev does not shift:

Initial list: 1->2->3->4->5 , with k=3

After first step: 2->1->3->4->5
After full reversal: 3->2->1->4->5
Note: The 'next' node for 'prev' is continually updated to 'current’s next, hence 'current' remains unchanged in a single batch swap.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the linked list.

Code

public class Reverse_Nodes_in_k_Group {

    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;

            ListNode prev = dummy;

            // count total nodes
            ListNode tmp = head;
            int count = 0;
            while (tmp != null) {
                count++;
                tmp = tmp.next;
            }

            // 1->2->3->4->5 , k=3
            // 2,1,3,4,5
            // 3,2,1,4,5
            // => always getting 1's next for prev's next => current (below) not changing in one-batch-swap

            // if only one node left, then no swap
            while (count >= k) {

                ListNode originalFirst = prev.next;

                int kcopy = k - 1; // @note: since current node is already counted as 1
                while (kcopy > 0) { // both prev and current, not changed in while loop

                    ListNode nextNextCopy = originalFirst.next.next;
                    ListNode firstInGroup = prev.next;

                    prev.next = originalFirst.next;
                    prev.next.next = firstInGroup;
                    originalFirst.next = nextNextCopy;

                    kcopy--;
                }

                // @note: update previous AND current. I forgot current...
                prev = originalFirst; // now current is the last one of this group
                count -= k;
            }

            return dummy.next;
        }
    }
}

//////

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = dummy;
        while (cur.next != null) {
            for (int i = 0; i < k && cur != null; ++i) {
                cur = cur.next;
            }
            if (cur == null) {
                return dummy.next;
            }
            ListNode t = cur.next;
            cur.next = null;
            ListNode start = pre.next;
            pre.next = reverseList(start);
            start.next = t;
            pre = start;
            cur = pre;
        }
        return dummy.next;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null, p = head;
        while (p != null) {
            ListNode q = p.next;
            p.next = pre;
            pre = p;
            p = q;
        }
        return pre;
    }
}

// OJ: https://leetcode.com/problems/reverse-nodes-in-k-group/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode h, *tail = &h;
        while (head) {
            auto prev = tail;
            int i = 0;
            for (auto p = head; i < k && p; ++i, p = p->next);
            if (i < k) {
                tail->next = head;
                break;
            }
            for (int i = 0; i < k && head; ++i) {
                auto node = head;
                head = head->next;
                node->next = prev->next;
                prev->next = node;
            }
            while (tail->next) tail = tail->next;
        }
        return h.next;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        '''
            for reverse 1->2->3->4->5, process is like
                1->None, 2->3->4->5
                2->1->None, 3->4->5
                3->2->1->None, 4->5
                4->3->2->1->None, 5
                5->4->3->2->1->None, None
        '''
        def reverseList(head):
            pre, p = None, head
            while p:
                pnext = p.next
                p.next = pre
                pre = p
                p = pnext
            return pre

        dummy = ListNode(next=head)
        pre = cur = dummy
        while cur.next:
            for _ in range(k):
                cur = cur.next
                if cur is None:
                    return dummy.next
            t = cur.next
            cur.next = None # cut from next k-group, so to reverseList() for current k-group
            start = pre.next
            pre.next = reverseList(start)
            start.next = t # so now 'start' is the last node of k-group
            pre = cur = start # same as the reset dummy before while loop
        return dummy.next

############

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
  def reverseKGroup(self, head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """

    def reverseList(head, k):
      pre = None
      cur = head
      while cur and k > 0:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
        k -= 1
      head.next = cur
      return cur, pre

    length = 0
    p = head
    while p:
      length += 1
      p = p.next
    if length < k:
      return head
    step = length / k
    ret = None
    pre = None
    p = head
    while p and step:
      next, newHead = reverseList(p, k)
      if ret is None:
        ret = newHead
      if pre:
        pre.next = newHead
      pre = p
      p = next
      step -= 1
    return ret

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	start, end := head, head
	for i := 0; i < k; i++ {
		if end == nil {
			return head
		}
		end = end.Next
	}
	res := reverse(start, end)
	start.Next = reverseKGroup(end, k)
	return res
}

func reverse(start, end *ListNode) *ListNode {
	var pre *ListNode = nil
	for start != end {
		tmp := start.Next
		start.Next, pre = pre, start
		start = tmp
	}
	return pre
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    let dummy = new ListNode(0, head);
    let pre = dummy;
    // pre->head-> ... ->tail-> next
    while (head != null) {
        let tail = pre;
        for (let i = 0; i < k; ++i) {
            tail = tail.next;
            if (tail == null) {
                return dummy.next;
            }
        }
        let t = tail.next;
        [head, tail] = reverse(head, tail);
        // set next
        pre.next = head;
        tail.next = t;
        // set new pre and new head
        pre = tail;
        head = t;
    }
    return dummy.next;
}

function reverse(head: ListNode, tail: ListNode) {
    let cur = head;
    let pre = tail.next;
    // head -> next -> ... -> tail -> pre
    while (pre != tail) {
        let t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    return [tail, head];
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = dummy;
        while (cur.next != null)
        {
            for (int i = 0; i < k && cur != null; ++i)
            {
                cur = cur.next;
            }
            if (cur == null)
            {
                return dummy.next;
            }
            ListNode t = cur.next;
            cur.next = null;
            ListNode start = pre.next;
            pre.next = ReverseList(start);
            start.next = t;
            pre = start;
            cur = pre;
        }
        return dummy.next;
    }

    private ListNode ReverseList(ListNode head) {
        ListNode pre = null, p = head;
        while (p != null)
        {
            ListNode q = p.next;
            p.next = pre;
            pre = p;
            p = q;
        }
        return pre;
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            let mut head = head;
            let mut pre = None;
            while let Some(mut node) = head {
                head = node.next.take();
                node.next = pre.take();
                pre = Some(node);
            }
            pre
        }

        let mut dummy = Some(Box::new(ListNode::new(0)));
        let mut pre = &mut dummy;
        let mut cur = head;
        while cur.is_some() {
            let mut q = &mut cur;
            for _ in 0..k - 1 {
                if q.is_none() {
                    break;
                }
                q = &mut q.as_mut().unwrap().next;
            }
            if q.is_none() {
                pre.as_mut().unwrap().next = cur;
                return dummy.unwrap().next;
            }

            let b = q.as_mut().unwrap().next.take();
            pre.as_mut().unwrap().next = reverse(cur);
            while pre.is_some() && pre.as_mut().unwrap().next.is_some() {
                pre = &mut pre.as_mut().unwrap().next;
            }
            cur = b;
        }
        dummy.unwrap().next
    }
}

# Definition for singly-linked list.
# class ListNode {
#     public $val;
#     public $next;
#     public function __construct($val = 0, $next = null)
#     {
#         $this->val = $val;
#         $this->next = $next;
#     }
# }

class Solution {
    /**
     * @param ListNode $head
     * @param int $k
     * @return ListNode
     */

    function reverseKGroup($head, $k) {
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $prevGroupTail = $dummy;

        while ($head !== null) {
            $count = 0;
            $groupHead = $head;
            $groupTail = $head;

            while ($count < $k && $head !== null) {
                $head = $head->next;
                $count++;
            }
            if ($count < $k) {
                $prevGroupTail->next = $groupHead;
                break;
            }

            $prev = null;
            for ($i = 0; $i < $k; $i++) {
                $next = $groupHead->next;
                $groupHead->next = $prev;
                $prev = $groupHead;
                $groupHead = $next;
            }
            $prevGroupTail->next = $prev;
            $prevGroupTail = $groupTail;
        }

        return $dummy->next;
    }
}

25 - Reverse Nodes in k-Group

25. Reverse Nodes in k-Group

Description

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

25. Reverse Nodes in k-Group

Description

Algorithm

Code

All Problems

All Solutions