86. 分隔链表
给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
思路:
该链表没有头结点,加上一个头结点方便插入和删除
遍历链表(结束条件为p!=null)
1)找到第一个不小于x的节点X并记录位置
2)X前的所有节点不需要改变
3)X后所有值小于x的节点均需按照与按原顺序插入到节点X之前
时间复杂度:遍历一次链表 O(N)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
//找到第一个>=x的节点位置P,将其后<=x的节点按照原来的顺序插入P之前
//该链表不包含头结点,先给该链表加一个头结点方便插入
ListNode new_head=new ListNode(Integer.MAX_VALUE);
new_head.next=head;
ListNode pre=new_head,p=new_head.next;
while(p!=null && p.val<x) {
pre=p;
p=p.next;
}
ListNode new_pre=pre,new_p=p;
while(new_p!=null) {
if (new_p.val<x) {
//将当前节点插入到第一个>=x的节点之前
new_pre.next=new_p.next;
pre.next=new_p;
new_p.next=p;
//更新第一个>x节点的前驱节点
pre=pre.next;
//继续向后遍历
new_p=new_pre.next;
continue;
}
new_pre=new_p;
new_p=new_p.next;
}
return new_head.next;
}
}