My O(n)/O(1) Solution


  • 6
    Y

    I use tail to keep track of the end point where the nodes before it are smaller than x.


    public ListNode partition(ListNode head, int x) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode p=dummy;
        ListNode tail=dummy;
        while(p!=null && p.next!=null){
            if(p.next.val>=x)
                p=p.next;
            else{
                if(p==tail){  // don't forget the edge cases when p==tail
                    tail=tail.next;
                    p=p.next;
                }
                else{
                    ListNode tmp=p.next;
                    p.next=tmp.next;
                    tmp.next=tail.next;
                    tail.next=tmp;
                    tail=tmp; // don't forget to move tail.
                }
            }
        }
        return dummy.next;
    }

  • 0
    S

    Pay attention to "Writing code? Select all code then click on the button to preserve code formatting.” above text editor.


  • 0

    here is my accepted python code using the same idea as you:

    class Solution:
        # @param head, a ListNode
        # @param x, an integer
        # @return a ListNode
        def partition(self, head, x):
    
            # use a dummy variant in case head is modified
            dummy=ListNode(0)
            dummy.next=head
            pre=post=dummy
            # test post.next.val to save variant post0
            while post!=None and post.next!=None:
                if post.next.val >=x:
                    post=post.next
                # post is always >=x, then we can cite post.next<x
                else:
                    # while pre==post, means while pre.next<x
                    if pre==post:
                        # this is for the beginning
                        pre=pre.next
                        post=post.next
                    # until we have pre<x, pre.next>=x,post>=x,post.next<x
                    else:
                        # ->...->pre->pre.next->...->post->post.next->...
                        # fix to ...->pre->post.next->pre.next->...->pre.next
                        # use tmp to simplify the process of pointer change
                        tmp=post.next
                        post.next=tmp.next
                        tmp.next=pre.next
                        pre.next=tmp
                        pre=tmp
          
            return dummy.next 

  • 0
    A

    My solution is almost the same as yours. I am just wondering if there is anyway to remove the if statement to check for the "p == tail" edge case.


Log in to reply
 

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