86. Partition List

三刷 07/2022

和一刷一样，又一次写出了cycle的bug

原因是larger half的最后一个点有可能是指向smaller half的某个点的

这样连接起来就会成环

所以要不然是向二刷的做法每一次都把后面的pointer切断，要么是一刷的做法把larger point.next设置为null

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Partition List.

Memory Usage: 42 MB, less than 83.95% of Java online submissions for Partition List.

class Solution {

    public ListNode partition(ListNode head, int x) {

        ListNode smallHead = new ListNode(0);

        ListNode pSmall = smallHead;

        ListNode largeHead = new ListNode(0);

        ListNode pLarge = largeHead;

        ListNode curr = head;

        while (curr != null) {

            if (curr.val < x) {

                pSmall.next = curr;

                pSmall = pSmall.next;

            } else {

                pLarge.next = curr;

                pLarge = pLarge.next;

            }

            curr = curr.next;

        }

        pLarge.next = null;

        pSmall.next = largeHead.next;

        return smallHead.next;

    }

}

二刷 05/2022

Runtime: 0 ms, faster than 100.00% of Java online submissions for Partition List.

Memory Usage: 43.2 MB, less than 13.90% of Java online submissions for Partition List.

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode partition(ListNode head, int x) {

        if (head == null) {

            return head;

        }

        ListNode less = new ListNode();

        ListNode greaterOrEqual = new ListNode();

        ListNode curr = head, lp = less, gp = greaterOrEqual;

        while (curr != null) {

            if (curr.val < x) {

                lp.next = curr;

                lp = lp.next;

                curr = curr.next;

                lp.next = null;

            } else {

                gp.next = curr;

                gp = gp.next;

                curr = curr.next;

                gp.next = null;

            }

        }

        lp.next = greaterOrEqual.next;

        return less.next; 

    }

}

一刷

Bug 最后largerCurr.next = null
否则会有cycle

100.00 % 
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode curr = head;
        head = new ListNode(0);
        ListNode largerHead = new ListNode(0);
        ListNode smallerCurr = head;
        ListNode largerCurr = largerHead;
        while (curr != null) {
            if (curr.val < x) {
                smallerCurr.next = curr;
                smallerCurr = smallerCurr.next;
            } else {
                largerCurr.next = curr;
                largerCurr = largerCurr.next;
            }
            curr = curr.next;
        }
        largerCurr.next = null;
        smallerCurr.next = largerHead.next;
        return head.next;
    }
}