86. 分隔链表
给你一个链表的头节点 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
思路:双指针+双链表(值大的放后面,值小的放前面,最后将大值链表指向空,否则产生环)
/** * 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) { ListNode dummyPre = new ListNode(-1); ListNode dummyPost = new ListNode(-1); ListNode res1 = dummyPre; ListNode res2 = dummyPost; while (head != null) { if (head.val >= x) { dummyPost.next = head; dummyPost = dummyPost.next; } else { dummyPre.next = head; dummyPre = dummyPre.next; } head = head.next; } // 将最大链表的最后一个指向空,不然会产生环,如示例1所示,5又指向了2 dummyPost.next = null; dummyPre.next = res2.next; return res1.next; } }