Java easy to understand solution


  • 1

    Idea is straight forward, scan the original list, move those item larger or equal to x to a new list. After the scan, connect the new list to the tail of original list. Note that although we are conceptually using a new list, we only used O(1) extra space since this is linked list not array.

    Java

    public class Solution{
        public ListNode partition(ListNode head, int x) {
            ListNode small = new ListNode(0);
            ListNode large = new ListNode(0);
            small.next = head;
            ListNode scanner = small;
            ListNode tail = large;
            while (scanner.next != null) {
                if (scanner.next.val >= x) {
                    tail.next = scanner.next;
                    scanner.next = scanner.next.next;
                    tail = tail.next;
                    tail.next = null;
                }
                else
                    scanner = scanner.next;
            }
            scanner.next = large.next;
            return small.next;
        }
    }
    

    Runtime: 1ms


Log in to reply
 

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