您现在的位置是:首页 >学无止境 >【刷题之路Ⅱ】LeetCode 86. 分隔链表网站首页学无止境
【刷题之路Ⅱ】LeetCode 86. 分隔链表
【刷题之路Ⅱ】LeetCode 86. 分隔链表
一、题目描述
原题连接: 86. 分隔链表
题目描述:
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:
输入: head = [1,4,3,2,5,2], x = 3
输出: [1,2,2,4,3,5]
示例 2:
输入: head = [2,1], x = 2
输出: [1,2]
提示:
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
二、解题
1、方法1——先分离再连接
1.1、思路分析
我们可以额外创建两个链表Less和Great,将节点值小于x的节点全都按顺序插入到Less中,将节点值大于等于x的节点全都按顺序插入到Great中。然后将这两条链表连接起来(Less的尾连接上Greate的头)即可,例如:
所以我们的代码思路很快就可以出来了,我们使用一个cur指针遍历链表中的节点,当cur->val < x时,就将cur尾插到Less链表中,否则就尾插到Great链表中。
但需要特别注意的是,在所有节点都遍历完后一定要确保Great链表的尾节点的next指向的要是空,因为如果Great尾插的最后一个节点不是原链表的最后一个节点的话,那么它的next将仍然连接着它原来的下一个节点:
如果不加以处理的话,最终的新链表就会出现一个环了:
1.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode *LessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *LessTail = NULL; // 记录Less链表的尾
struct ListNode *GreatHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *GreatTail = NULL; // 记录Great链表的尾
struct ListNode *cur = head;
LessTail = LessHead;
GreatTail = GreatHead;
// 创建带头结点的链表是为了更好的处理链表为空的情况
while (cur) {
if (cur->val < x) {
LessTail->next = cur;
LessTail = LessTail->next;
} else {
GreatTail->next = cur;
GreatTail = GreatTail->next;
}
cur = cur->next;
}
GreatTail->next = NULL;
LessTail->next = GreatHead->next;
return LessHead->next;
}
时间复杂度:O(n),n为链表的长度,我们只需要遍历完链表中的所有节点就可以完成,所以时间复杂度为O(n)。
空间复杂度:O(1),我们们只需要用到常数级的额外空间。
2、方法2——将较大的节点后移
2.1、思路分析
还有一个不用创建新链表的方式就是将节点值大于等于x的节点尾插到链表的最后:
这样当我们把所有节点值大于等于x的节点都尾插完后,其实也是满足题目要求的相对位置不变的。
而对于结束的条件,我们可以优先记录好链表的长度len,然后当我们遍历的节点数等于len时就可以结束了。
所以我们需要优先记录的信息有两个分别是链表的长度len和尾节点tail。
2.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
struct ListNode* partition(struct ListNode* head, int x) {
if (NULL == head || NULL == head->next) {
return head;
}
int len = 1;
struct ListNode *tail = head;
while (tail->next) {
len++;
tail = tail->next;
}
struct ListNode *dumbNode = (struct ListNode*)malloc(sizeof(struct ListNode));
if (NULL == dumbNode) {
perror("malloc fail");
return NULL;
}
dumbNode->next = head;
struct ListNode *cur = head;
int count = 0;
struct ListNode *pre = dumbNode; // 记录cur的前一个节点
struct ListNode *next = cur->next; // 记录cur的下一个节点
while (count < len) {
count++;
next = cur->next;
if ((cur->val >= x) && (cur->next)) { // cur的val大于等于x且cur不为最后一个节点
pre->next = next;
// 尾插
tail->next = cur;
cur->next = NULL;
tail = tail->next;
} else {
pre = pre->next;
}
cur = next;
}
return dumbNode->next;
}
时间复杂度:O(n),n为链表的长度。
空间复杂度:O(1),我们只需要用到常数级的额外空间。