My iterative solution


  • 0
    7

    But it runs slow , can anyone speed it up?

    public class Solution {
        public ListNode sortList(ListNode head) {
            ListNode dummy = new ListNode(0);
            ListNode pointer, l1, l2, next;
            int k = 1;
            int kl1, kl2, times;
            dummy.next = head;
            do {
                pointer = dummy;
                times = 0;
                while (pointer.next != null ) {
                    l1 = pointer;
                    kl1 = kl2 = k;
                    while (kl1 > 0 && l1.next != null) {
                        l1 = l1.next;
                        kl1--;
                    }
                    l2 = l1;
                    while (kl2 > 0 && l2.next != null) {
                        l2 = l2.next;
                        kl2--;
                    }
                    next = l2.next;
                    l2 = l1.next;
                    l1 = pointer.next;
                    kl1 = k - kl1;
                    kl2 = k - kl2;
                    while (kl1 != 0 || kl2 != 0) {
                        if (kl2 == 0 || (kl1 != 0 && l1.val < l2.val)) {
                            pointer.next = l1;
                            l1 = l1.next;
                            kl1--;
                        } else {
                            pointer.next = l2;
                            l2 = l2.next;
                            kl2--;
                        }
                        pointer = pointer.next;
                    }
                    pointer.next = next;
                    times++;
                }
                k = k * 2;
            } while (times > 1);
            return dummy.next;
        }
    }

Log in to reply
 

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