题目：
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
?
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
解析：
在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于?x，另一个链表中的元素都大于等于?x，最后再把这两条链表接到一起，就得到了题目想要的结果。
整体逻辑和合并有序链表非常相似，细节直接看代码吧。
注意遍历结束后，我们将large 的next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 xx 的节点，我们需要切断这个引用，不然会造成循环链表！
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
// 存放小于 x 的链表的虚拟头结点
ListNode dummy1 = new ListNode(-1);
// 存放大于等于 x 的链表的虚拟头结点
ListNode dummy2 = new ListNode(-1);
// p1, p2 指针负责生成结果链表
ListNode p1 = dummy1;
ListNode p2 = dummy2;
// p 负责遍历原链表
ListNode p = head;
while(p != null){
if(p.val < x){
p1.next = p;
p1 = p1.next;
}else{
p2.next = p;
p2 = p2.next;
}
p = p.next;
}
//注意将dummy2链表末尾指向null
p2.next = null;
// 连接两个链表
p1.next = dummy2.next;
return dummy1.next;
}
}
|