Java O(n) elegant code solution


  • 10

    why use while(true) loop? We don't know if there is k nodes left out in advance. So we advance tail for k steps to check for that. If there is no k nodes, the program exits from there.

     public class Solution {
            public ListNode reverseKGroup(ListNode head, int k) {
                if (k <= 1 || head == null || head.next == null)
                    return head;
                ListNode newHead = new ListNode(0);
                newHead.next = head;
                ListNode prev, start, then, tail;
                tail = prev = newHead;
                start = prev.next;
                while (true) {
                    // check if there's k nodes left-out
                    for (int i = 0; i < k; i++) {
                        tail = tail.next;
                        if (tail == null)
                            return newHead.next;
                    }
                    // reverse k nodes
                    for (int i = 0; i < k - 1; i++) {
                        then = start.next;
                        start.next = then.next;
                        then.next = prev.next;
                        prev.next = then;
                    }
                    tail = prev = start;
                    start = prev.next;
                }
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.