概览：
前置知识：理解链表及其基本调整 建议：做过这个题86. 分隔链表的同学跳过
给你一个链表的头节点 head 和一个特定值 x
请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前
你应当 保留 两个分区中每个节点的初始相对位置
链表题目在笔试、面试中的意义就是检验coding能力如何
更难的题目会在【必备】课程里讲述
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
1
2
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
1
2
输入：head = [2,1], x = 2
输出：[1,2]
提示：
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
重要思路：哑节点
准备2个哑节点，作为小于x的链表的头和大于等于x的链表的头。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 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 lessDummy = new ListNode(0);
ListNode equalBiggerDummy = new ListNode(0);
ListNode lessCur = lessDummy, equalBiggerCur = equalBiggerDummy, cur = head;
while (cur != null) {
if (cur.val < x) {
lessCur.next = cur;
lessCur = lessCur.next;
}else {
equalBiggerCur.next = cur;
equalBiggerCur = equalBiggerCur.next;
}
cur = cur.next;
}
equalBiggerCur.next = null;
lessCur.next = equalBiggerDummy.next;
return lessDummy.next;
}
}
总结：
- 用两个哑节点（dummy node）分别作为小于部分和大于等于部分的头
- 分别维护两个Cur指针处理节点连接
- 最后连接两个部分并返回结果
补充1:力扣328. 奇偶链表
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
示例 1:
1
2
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:
1
2
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
提示:
n ==链表中的节点数0 <= n <= 104-106 <= Node.val <= 106
解法
和上面86题思路几乎一致
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 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 oddEvenList(ListNode head) {
ListNode oddHead = new ListNode(0), evenHead = new ListNode(0);
ListNode oddCur = oddHead, evenCur = evenHead, cur = head;
int i = 1;
while (cur != null){
if (i % 2 == 1) {
oddCur.next = cur;
oddCur = oddCur.next;
} else {
evenCur.next = cur;
evenCur = evenCur.next;
}
i++;
cur = cur.next;
}
evenCur.next = null;
oddCur.next = evenHead.next;
return oddHead.next;
}
}
