86. 分隔链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 112 阅读时长 ≈ 1 分钟

考点

  • 链表的裁剪

题解

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的节点，一个大链表按序存储剩余节点，再将大链表接在小链表尾部即可