第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0086. 分隔链表

题目地址(86. 分隔链表)

题目描述

1
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
2
3
你应当保留两个分区中每个节点的初始相对位置。
4
5
6
7
示例:
8
9
输入: head = 1->4->3->2->5->2, x = 3
10
输出: 1->2->2->4->3->5
Copied!

前置知识

  • 链表

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

  • 设定两个虚拟节点,dummyHead1 用来保存小于该值的链表,dummyHead2 来保存大于等于该值的链表
  • 遍历整个原始链表,将小于该值的放于 dummyHead1 中,其余的放置在 dummyHead2 中
遍历结束后,将 dummyHead2 插入到 dummyHead1 后面
86.partition-list

关键点解析

  • 链表的基本操作(遍历)
  • 虚拟节点 dummy 简化操作
  • 遍历完成之后记得currentL1.next = null;否则会内存溢出
如果单纯的遍历是不需要上面操作的,但是我们的遍历会导致 currentL1.next 和 currentL2.next 中有且仅有一个不是 null, 如果不这么操作的话会导致两个链表成环,造成溢出。

代码

  • 语言支持: Javascript,Python3, CPP
1
/**
2
* @param {ListNode} head
3
* @param {number} x
4
* @return {ListNode}
5
*/
6
var partition = function (head, x) {
7
const dummyHead1 = {
8
next: null,
9
};
10
const dummyHead2 = {
11
next: null,
12
};
13
14
let current = {
15
next: head,
16
};
17
let currentL1 = dummyHead1;
18
let currentL2 = dummyHead2;
19
while (current.next) {
20
current = current.next;
21
if (current.val < x) {
22
currentL1.next = current;
23
currentL1 = current;
24
} else {
25
currentL2.next = current;
26
currentL2 = current;
27
}
28
}
29
30
currentL2.next = null;
31
32
currentL1.next = dummyHead2.next;
33
34
return dummyHead1.next;
35
};
Copied!
Python3 Code:
1
class Solution:
2
def partition(self, head: ListNode, x: int) -> ListNode:
3
"""在原链表操作,思路基本一致,只是通过指针进行区分而已"""
4
# 在链表最前面设定一个初始node作为锚点,方便返回最后的结果
5
first_node = ListNode(0)
6
first_node.next = head
7
# 设计三个指针,一个指向小于x的最后一个节点,即前后分离点
8
# 一个指向当前遍历节点的前一个节点
9
# 一个指向当前遍历的节点
10
sep_node = first_node
11
pre_node = first_node
12
current_node = head
13
14
while current_node is not None:
15
if current_node.val < x:
16
# 注意有可能出现前一个节点就是分离节点的情况
17
if pre_node is sep_node:
18
pre_node = current_node
19
sep_node = current_node
20
current_node = current_node.next
21
else:
22
# 这段次序比较烧脑
23
pre_node.next = current_node.next
24
current_node.next = sep_node.next
25
sep_node.next = current_node
26
sep_node = current_node
27
current_node = pre_node.next
28
else:
29
pre_node = current_node
30
current_node = pre_node.next
31
32
return first_node.next
Copied!
CPP Code:
1
class Solution {
2
public:
3
ListNode* partition(ListNode* head, int x) {
4
ListNode dummy, geHead, *ltTail = &dummy, *geTail = &geHead;
5
while (head) {
6
auto p = head;
7
head = head->next;
8
if (p->val < x) {
9
ltTail->next = p;
10
ltTail = p;
11
} else {
12
geTail->next = p;
13
geTail = p;
14
}
15
}
16
ltTail->next = geHead.next;
17
geTail->next = NULL;
18
return dummy.next;
19
}
20
};
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。