0%

[Leetcode]86. Partition List(C++)

题目描述

题目链接:86. Partition List

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

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 的,并且两部分内部相对顺序保持不变。思路比较简单,遍历一次原链表,用两个链表分成存储这两部分,最后将前者的尾部和后者的头部相连即可,注意一下最后需要将第二段链表的尾部的下一个节点置空。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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