题目与示例
题目
示例
算法思路
原链表顺序遍历，将大于等于x的结点链接为一个链表，小于x的结点链接为一个链表，最后再将两个链表链接起来。
代码实现
public ListNode partition(ListNode head, int x) {
ListNode leftHead=null,leftTail=null;
ListNode rightHead=null,rightTail=null;
while(head!=null){
ListNode nex=head.next; //将链表的每一个结点都拆下来
head.next=null;
if(head.val<x){
if(leftHead==null){ //该结点的值小于x
leftHead=new ListNode(head.val);
leftTail=leftHead;
}else {
leftTail.next=head;
leftTail=leftTail.next;
}
}
else{ //该结点的值大于等于x
if(rightHead==null){
rightHead=new ListNode(head.val);
rightTail=rightHead;
}else{
rightTail.next=head;
rightTail=rightTail.next;
}
}
head=nex;
}
if(leftHead==null) return rightHead; //所有结点值都大于等于x的情况
leftTail.next=rightHead;
return leftHead;
}
