25. Reverse Nodes in k-Group (Hard)


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.


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


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


class Solution {

    // The key idea is to sort out the length of the given list first. Then reverse the legitimate groups
    // only, in other words, you don't have to care about the nodes that can't form a group of size k.
    // Finally, handle each group separately. It is advised to reverse elements in the group as the way
    // insertion sort does. The trick is to prepend the element at the head in each iteration.

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        int len = 0;

        ListNode node = head;
        while (node != null) {
            node = node.next;

        // k = 3, dummy->n1->n2->n3->n4
        head = dummy;

        // only on the event that the size of group is k, then it can be reversed
        for (int i = 0; i < len / k * k; i++) {
            if (i % k == 0) {
                reverseGroupElements(head, k);

            head = head.next;

        return dummy.next;

    private ListNode reverseGroupElements(ListNode head, int k) {
        if (head.next == null) {
            return null;

        // head->p1->p2->p3->p4, k = 3
        // head->p2->p1->p3->p4
        // head->p3->p2->p1->p4

        ListNode p1 = head.next;
        ListNode p2 = p1.next;

        // If it is allowed to swap values in node, it will be much easier.
        for (int i = 1; i < k; i++) {
            if (p2 == null) {

            p1.next = p2.next;

            // p2.next should be head.next, rather than p1
            p2.next = head.next;

            head.next = p2;

            p2 = p1.next;

        return head.next;

Incorrect Solutions


Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-27 10:51:07

results matching ""

    No results matching ""