86. 分隔链表

考点

  • 链表的裁剪

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *dummySmall = new ListNode(-1), *curSmall = dummySmall;
ListNode *dummyLarge = new ListNode(-1), *curLarge = dummyLarge;
while (head != nullptr) {
if (head->val < x) {
curSmall->next = head;
curSmall = curSmall->next;
} else {
curLarge->next = head;
curLarge = curLarge->next;
}
head = head->next;
}
curSmall->next = dummyLarge->next;
curLarge->next = nullptr;
return dummySmall->next;
}
};

思路

一个小链表按序存储值小于x的节点,一个大链表按序存储剩余节点,再将大链表接在小链表尾部即可