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.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
题目
给定一个链表，一个数x,把这个链表以x分界，左边是小于x的数，右边是大于等于x的数，排完后元素的相对位置不变，只是大小分区了。
思路
最直观的想法，新建两个链表，一个存小于x的，一个存大于x的，最后再把两个链表合并。
代码
public ListNode partition(ListNode head, int x) {
/*
* Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
*/
if (head==null||head.next==null) {
return head;
}
ListNode newHeadSmall=new ListNode(-1);
ListNode newHeadBig=new ListNode(-1);
ListNode curSmall=newHeadSmall;
ListNode curBig=newHeadBig;
while (head!=null) {
if (head.val<x) {//遍历head
curSmall.next=head;//小就连到small上
curSmall=curSmall.next;
head=head.next;
}else {//大就连到big上
curBig.next=head;
curBig=curBig.next;
head=head.next;
}
}
curBig.next=null;//最后把big结尾指向空
curSmall.next=newHeadBig.next;//small结尾连接big
return newHeadSmall.next;//返回small
}
