patternjavaModerate

Reversing k-sized sequences in a linked-list

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

sizedreversinglistlinkedsequences

Problem

Here is my solution to this problem; please be brutally honest/strict, if I would have written this code, in a 45 minute interview, what would you think? (I am aiming for Google,Facebook).

Here is the problem I solved:

*Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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 nodes, only nodes itself may be changed.

For 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

Thanks.

```
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}

public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int count=1;
ListNode cursor = head;
ListNode current = null;
ListNode remainingHalf = null;
Queue linkQueue = new LinkedList();

if(head==null){
return null;
}

if(kfindSize(head)){
return head;
}
if(k==2){
return reverse(head);
}

while(cursor!=null || cursor.next!=null){

while(count!=k){
if(cursor!=null){
cursor = cursor.next;
}
count++;
}
if(cursor!=null){
remainingHalf = cursor.next;
cursor.next=null;

ListNode partial = reverse(head);
linkQueue.add(partial);

cursor = remainingHalf;
head = remainingHalf;
}
else{
linkQueue.add(remainingHalf);
break;
}
count=1;
if(cursor==null || cursor.next==null){
linkQueue.add(remainingHalf);
break;
}

}
boolean headFlag=false;
ListNode toRet=null;
while(!linkQueue.isEmpty()){

Solution

Brutally honest?

If this is an interview, and you provide this line of code:

Queue linkQueue = new LinkedList();

Your resume gets put in the pile of 'ignore this person if they apply again'... ;-)

Genercis have been around for a decade now (introduced in 2004). You should know them, and use them.
Class Model

The ListNode should not be a public class. The information should be encapsulated within a single class, and not exposed. There should be no need for a user to have to supply a 'head' node to the public ListNode reverseKGroup(ListNode head, int k). This should be a class, say ReversingList which has a method reverseK(int k), and then provides a way to retrieve the re-ordered data (which may be in the format of a new ReversingList instance.
Algorithm

Your algorithm looks really complicated. There should be no need to scan the list before processing it. That indicates some serious inefficiencies.

Additionally, relying on the LinkedList class is a bit of a cheat... but, if you are going to use it, then you may as well go the whole hog, and use its reverse function... (descendingIterator())
How would I do it?

This was the original title of the question... well, how about:

public class SolutionList {

    private static final class ListNode {
        private final int val;
        private ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        @Override
        public String toString() {
            return "ListNode " + val;
        }
    }

    // use relatively common trick of having a dummy head node.
    private final ListNode head = new ListNode(0);

    public SolutionList() {
        // default constructor does nothing.
    }

    public void add(int v) {
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = new ListNode(v);
    }

    public void addAll(SolutionList toadd) {
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        ListNode their = toadd.head.next;
        while (their != null) {
            tail.next = new ListNode(their.val);
            tail = tail.next;
            their = their.next;
        }
    }

    public void reverseKInPlace(final int k) {
        if (k = 0) {
                    mark.next = stack[depth];
                    mark = mark.next;
                }
                depth = 0;
            }
            node = nxt;
        }
        if (depth > 0) {
            mark.next = stack[0];
        }

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("SolutionList [");
        ListNode node = head.next;
        while (node != null) {
            sb.append(node.val).append(", ");
            node = node.next;
        }
        if (head.next != null) {
            sb.setLength(sb.length() - 2);
        }
        sb.append("]");
        return sb.toString();
    }

    public SolutionList reverseK(final int k) {
        SolutionList copy = new SolutionList();
        copy.addAll(this);
        copy.reverseKInPlace(k);
        return copy;
    }

    public static void main(String[] args) {
        int[] vals = { 1, 2, 3, 4, 5 };
        SolutionList soln = new SolutionList();
        for (int v : vals) {
            soln.add(v);
        }
        System.out.println(soln);
        System.out.println("Reverse 2 " + soln.reverseK(2));
        System.out.println("Reverse 3 " + soln.reverseK(3));
    }

}

Code Snippets

Queue linkQueue = new LinkedList();

public class SolutionList {

    private static final class ListNode {
        private final int val;
        private ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        @Override
        public String toString() {
            return "ListNode " + val;
        }
    }

    // use relatively common trick of having a dummy head node.
    private final ListNode head = new ListNode(0);

    public SolutionList() {
        // default constructor does nothing.
    }

    public void add(int v) {
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = new ListNode(v);
    }

    public void addAll(SolutionList toadd) {
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        ListNode their = toadd.head.next;
        while (their != null) {
            tail.next = new ListNode(their.val);
            tail = tail.next;
            their = their.next;
        }
    }

    public void reverseKInPlace(final int k) {
        if (k <= 1 || head.next == null) {
            return;
        }
        ListNode[] stack = new ListNode[k];
        int depth = 0;
        ListNode node = head.next;
        ListNode mark = head;
        while (node != null) {
            ListNode nxt = node.next;
            stack[depth++] = node;
            if (depth == k) {
                while (--depth >= 0) {
                    mark.next = stack[depth];
                    mark = mark.next;
                }
                depth = 0;
            }
            node = nxt;
        }
        if (depth > 0) {
            mark.next = stack[0];
        }

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("SolutionList [");
        ListNode node = head.next;
        while (node != null) {
            sb.append(node.val).append(", ");
            node = node.next;
        }
        if (head.next != null) {
            sb.setLength(sb.length() - 2);
        }
        sb.append("]");
        return sb.toString();
    }

    public SolutionList reverseK(final int k) {
        SolutionList copy = new SolutionList();
        copy.addAll(this);
        copy.reverseKInPlace(k);
        return copy;
    }

    public static void main(String[] args) {
        int[] vals = { 1, 2, 3, 4, 5 };
        SolutionList soln = new SolutionList();
        for (int v : vals) {
            soln.add(v);
        }
        System.out.println(soln);
        System.out.println("Reverse 2 " + soln.reverseK(2));
        System.out.println("Reverse 3 " + soln.reverseK(3));
    }

}

Context

StackExchange Code Review Q#43464, answer score: 13

Revisions (0)

No revisions yet.