LeetCode 0086 - Partition List
# Hints
- 链表 + 双指针扫描
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a linked list and a value , partition it such that all nodes less than come before nodes greater than or equal to .
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
# 题意
给定一个单链表和一个整数 ,要求重新划分节点顺序,使得值小于 的节点都出现在值大于等于 的节点之前,且要求保持值小于(大于等于) 的节点在原链表中的相对顺序不变。
# 题解
水题,我们只需顺序遍历链表,并分别构造两个新的链表来依次记录值小于和值大于等于的节点,最后将两个新的链表首尾相接即可。
# AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode * next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode * next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode * partition(ListNode * head, int x) {
// 初始化
ListNode * head1 = new ListNode();
ListNode * head2 = new ListNode();
// 遍历
ListNode * p = head;
ListNode * l1 = head1;
ListNode * l2 = head2;
while (p != nullptr) {
ListNode * q = p->next;
insert_back((p->val < x ? l1 : l2), p);
p = q;
}
// 返回
l1->next = head2->next;
ListNode * res = head1->next;
//delete head1;
//delete head2;
return res;
}
// 插入尾部
void insert_back(ListNode * & l, ListNode * p) {
l->next = p;
l = l->next;
p->next = nullptr;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01