Easy understand and easy code in Java


  • 1
    P
            ListNode smallHead = new ListNode(x);//x is any int
            ListNode smallIndex = smallHead;
            ListNode bigHead = new ListNode(x);
            ListNode bigIndex = bigHead;
            while (head != null) {
                ListNode tmp = head;
                if (head.val < x) {
                    smallIndex.next = tmp;
                    smallIndex = smallIndex.next;
                } else {
                    bigIndex.next = tmp;
                    bigIndex = bigIndex.next;
                }
                head = head.next;
                tmp.next = null;
            }
            smallIndex.next = bigHead.next;
            return smallHead.next;
    

    Basic idea is to split one array to two arrays, finally connect the two arrays


  • 0
    A

    Hi, sorry to bother you, but why should we add "ListNode tmp = head;" and "tmp.next = null;"
    I tried without these two lines, which will cause memory limit exceed problem. but why? Thanks very much;


  • 0
    L

    Take 1->4->3->2->5->2 as example, if you don't do that, you will find that bigHead list is like :
    x->4->3->5->2. In this case, your final list will form a loop~


Log in to reply
 

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