Java, nonrecursive, space complexity O(1)


  • 0
    A

    To move the end, and to reverse the nodes between start and end (not included), I used two help functions. So the structure should be more clear.

    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || k == 0) return null;
            if (k==1)                   return head;
            ListNode sentinel = new ListNode(0), start = sentinel, end = head;
            sentinel.next = head;
            while (true) {
                try {end = move(end, k);}
                catch (Exception e) {break;}
                start = reverse(start, end);
            }
            return sentinel.next;
        }
    
        private ListNode move(ListNode end, int k) {
            for (int i = 0; i < k; i++) {
                if (end == null) throw new IllegalArgumentException();
                end = end.next;
            }
            return end;
        }
        private ListNode reverse(ListNode start, ListNode end) {
            ListNode pre = end, cur = start.next, nextStart = cur;
            while (cur != end) {
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            start.next = pre;
            return nextStart;
        }
    

Log in to reply
 

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