题目描述
题目链接:86. Partition List
Given the
head
of a linked list and a valuex
, partition it such that all nodes less thanx
come before nodes greater than or equal tox
.You should preserve the original relative order of the nodes in each of the two partitions.
例子
例子 1
Input:
head = [1,4,3,2,5,2], x = 3
Output:[1,2,2,4,3,5]
例子 2
Input:
head = [2,1], x = 2
Output:[1,2]
Constraints
- The number of nodes in the list is in the range
[0, 200]
.-100 <= Node.val <= 100
-200 <= x <= 200
解题思路
这道题要求给定一个节点和一个值 x
,将链表分成两部分:小于 x
和大于等于 x
的,并且两部分内部相对顺序保持不变。思路比较简单,遍历一次原链表,用两个链表分成存储这两部分,最后将前者的尾部和后者的头部相连即可,注意一下最后需要将第二段链表的尾部的下一个节点置空。代码如下:
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* less_list = new ListNode();
ListNode* less_tail = less_list;
ListNode* greater_list = new ListNode();
ListNode* greater_tail = greater_list;
ListNode* curr = head;
while (curr) {
if (curr->val < x) {
less_tail->next = curr;
less_tail = curr;
} else {
greater_tail->next = curr;
greater_tail = curr;
}
curr = curr->next;
}
less_tail->next = greater_list->next;
return less_list->next;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 86.PartitionList.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions