My not-so-short but clear solution


  • 0
    Y

    In my opinion data structure related questions on Leetcode are not so hard. Especially linked list and tree related questions.

    My solution basically loops through the list, find k-groups one by one and reverse them, then connect the previous node (if any) to the head of reversed group. Not so short, but very straightforward, easy to understand, and it works!

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || head.next == null) return head;
            // for the first k group, perv = null, for the rest, simply connect prev to head of reversed group
            ListNode prev = null, cur = head, head2 = null;
            int num = k;
            while (cur != null) {
                ListNode begin = cur, end = null;
                while (cur.next != null && num > 1) {   // cur.next != null includes last non-null node
                    cur = cur.next;
                    num--;
                }
                // if num > 1 then k > available nodes, either return head or connect last group and return head2
                if (num > 1) {
                    if (head2 == null) {
                        return head;
                    } else if (prev != null) {
                        prev.next = begin;
                    }
                    return head2;
                }
                end = cur;
                cur = cur.next;  // need to update cur here to avoid mistakes later on
                reverse(begin, end);
                if (head2 == null) {
                    head2 = end;
                }
                if (prev != null) {
                    prev.next = end;   
                }
                prev = begin;
                num = k;
            }
            return head2;
        }
        
        // can use void return type
        private ListNode reverse(ListNode begin, ListNode end) {
            if (begin == end) {
                return end;
            }
            ListNode temp = reverse(begin.next, end);
            begin.next.next = begin;
            begin.next = null;
            return temp;
        }
    }
    

Log in to reply
 

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