8 ms solution, only access every node one time except the nodes in the tail


  • 0
    F
     public ListNode reverseKGroup(ListNode head, int k) {
            if (k <= 1 || head == null || head.next == null) return head;
            ListNode curStart = head;
            ListNode preStart = null;
            ListNode pre = head;
            ListNode cur = head.next;
            ListNode tmp = null;
            ListNode res = null;
            int count = 2;
            while (cur != null) {
                tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
                if (count == k) {
                    if (res == null) {
                        res = pre;
                    } else {
                        preStart.next = pre;
                    }
                    preStart = curStart;
                    curStart = cur;
                    pre = cur;
                    if (cur == null || cur.next == null){
                        preStart.next = cur;
                        return res;
                    }
                    cur = cur.next;
                    count = 2;
                    continue;
                }
                count++;
            }
            
            reverse(pre, curStart);
            if (preStart != null) preStart.next = curStart;
            if (res == null) res = curStart;
            return res;
        }
        private void reverse(ListNode from, ListNode to) {
            ListNode cur = from.next;
            from.next = null;
            ListNode tmp = null;
            while (cur != to) {
                tmp = cur.next;
                cur.next = from;
                from = cur;
                cur = tmp;
            }
        }

Log in to reply
 

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