One pass , O (n) , easy to follow instructions


  • 0
    O

    Essentially, we need to build 2 lists. One whose values are < than x and the other whose values are >= x. Maintain head and tail for both the list.
    Drop the anchor node when a node.val > x for the first time. This anchor node is the head of the list whose values are >= x
    If there is no anchor node, keep expanding the previous list.
    There are 4 cases to consider

    Case 1 : CurrentNode.Val < x and null == anchor node : A null anchor node means, we have not found any node whose value is >= x. So, not much to do, just expand the prev

    Case 2: CurrentNode.Val > x and null == anchor node : This means, we have found our first node whose value >= x, make this the anchor node. Essentially, make this node the head of the list whose values are >= x

    Case 3 : CurrentNode.Val > x and null != anchor node : Another node whose value >=x ... since anchor node is not null, just add this node to tail of the anchor node list.

    Case 4 ( Most important case) : CurrentNode.Val < x and null == anchor node
    This means, we need to move the current node to the list depicted by the prev and then reconnect all the node. Looks at the code to get a better understanding of all the connections

        public ListNode partition(ListNode head, int x) {
            if (null == head){
                return null;
            }
    
            ListNode prevHead = new ListNode(0);
            prevHead.next = head;
            ListNode prevCur = prevHead;
    
            ListNode anchor = null;
            ListNode anchorCur = null;
    
            ListNode cur = head;
    
            while (null != cur){
    
                if (cur.val < x && null == anchor){
                    prevCur = cur;
                    cur = cur.next;
                }else if (cur.val >= x && null == anchor){
                    anchor = cur;
                    anchorCur = anchor;
                    cur = cur.next;
                }else if (cur.val >= x && null != anchor){
                    anchorCur = cur;
                    cur = cur.next;
                }else {
                    ListNode nxt = cur.next;
                    prevCur.next = cur;
                    cur.next = anchor;
                    anchorCur.next = nxt;
                    cur = nxt;
                    prevCur = prevCur.next;
                }
            }
    
            return prevHead.next;
        }
    
    

Log in to reply
 

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