# My O(n)/O(1) Solution

• 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);
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;
}``````

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

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

``````class Solution:
# @param x, an integer
# @return a ListNode

# use a dummy variant in case head is modified
dummy=ListNode(0)
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 ``````

• 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.

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