86. 分隔鏈表
問(wèn)題
給定一個(gè)鏈表和一個(gè)特定值 蜘腌，對(duì)鏈表進(jìn)行分隔，使得所有小于
的節(jié)點(diǎn)都在大于或等于
的節(jié)點(diǎn)之前嚷那。
你應(yīng)當(dāng)保留兩個(gè)分區(qū)中每個(gè)節(jié)點(diǎn)的初始相對(duì)位置咆耿。
示例:
輸入:
輸出:
解法
新建兩個(gè)，其中一個(gè)保存所有小于
的節(jié)點(diǎn)故硅，另一個(gè)保存所有大于等于
的節(jié)點(diǎn)庶灿。最后拼接兩個(gè)鏈表就行了。
代碼
java實(shí)現(xià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) {
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;
}
}
整體也沒(méi)什么難度吃衅。需要注意的就是在
