86. 分隔链表
问题
给定一个链表和一个特定值 ，对链表进行分隔，使得所有小于
的节点都在大于或等于
的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入:
输出:
解法
新建两个，其中一个保存所有小于
的节点，另一个保存所有大于等于
的节点。最后拼接两个链表就行了。
代码
java实现
/**
* 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) {
ListNode dummy1 = new ListNode(1);
ListNode dummy2 = new ListNode(1);
ListNode node1 = dummy1;
ListNode node2 = dummy2;
while(head != null) {
if (head.val < x) {
node1.next = head;
head = head.next;
node1 = node1.next;
node1.next = null;
} else {
node2.next = head;
head = head.next;
node2 = node2.next;
node2.next = null;
}
}
node1.next = dummy2.next;
return dummy1.next;
}
}
整体也没什么难度。需要注意的就是在
