您现在的位置是:首页 >学无止境 >【刷题之路Ⅱ】LeetCode 86. 分隔链表网站首页学无止境

【刷题之路Ⅱ】LeetCode 86. 分隔链表

林先生-1 2024-06-14 00:01:02
简介【刷题之路Ⅱ】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),我们只需要用到常数级的额外空间。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。