Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given
return
Given
1->4->3->2->5->2
and x = 3,return
1->2->2->4->3->5
.
Solution:O(n)
public class Solution { public ListNode partition(ListNode head, int x) { ListNode dummys = new ListNode(0); ListNode dummyb = new ListNode(0); ListNode curs = dummys; ListNode curb = dummyb; while(head!=null){ if(head.val <x){ curs.next = head; curs = curs.next; }else{ curb.next = head; curb = curb.next; } head = head.next; } curs.next = dummyb.next; curb.next = null; // be careful this return dummys.next; } }
沒有留言:
張貼留言