1 题目
给你一个链表的头节点 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
2 解答
还是先找到第一个节点的前一个节点，采用头插法把后边的小于的移前来，跟前两篇的头插法有一点不一样的就是 preNode 在今天这道题里因为要保持元素的相对位置，所以 preNode 是会向后移动的，也就是每往前插入一个 preNode = preNode.next，preNode也会同时移动一个元素哈：
/** * 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) { // write your code here if (head == null) return head; // 先找到大于等于 x 的第一个节点的前一个节点 // 然后对后续的元素采取头插法即可 // 先加一个空的头节点，方便进行遍历 ListNode emptyNode = new ListNode(0); emptyNode.next = head; // preNode 指向 大于等于 x 的节点的前一个节点 ListNode preNode = null; // 遍历 while (emptyNode != null) { // 下一个节点 ListNode nextNode = emptyNode.next; // 下一个节点的 val 如果和 x 相等 if (nextNode != null && nextNode.val >= x) { // 将 preNode 指向当前的 emptyNode 即前一个节点 preNode = emptyNode; // 找到了就跳出循环 break; } // 继续向后遍历 emptyNode = emptyNode.next; } boolean headChange = head.val >= x; // 如果 preNode 为空 说明没有大于等于 x 的直接返回吧 if (preNode == null) return head; // 不为空话就需要把 preNode 后边的 小于 x 的节点头插法进来 ListNode node = preNode, resNode = preNode; while (node != null) { ListNode nextNode = node.next; // 如果节点的 val 小于 x if (nextNode != null && nextNode.val < x) { // 前插法进来 node.next = nextNode.next; nextNode.next = preNode.next; preNode.next = nextNode; preNode = preNode.next; continue; } // 向后移动 node = node.next; } return headChange ? resNode.next : head; } }
加油。