【链表OJ题(六)】链表分割

2023-03-30

null next cur

📝个人主页：@Sherry的成长之路🏠学习社区：Sherry的成长之路（个人社区）📖专栏链接：数据结构🎯长路漫漫浩浩，万事皆有期待文章目录链表OJ题(六)1.链表分割思路一带哨兵位的头结点思路二不强行加头结点7.总结：上一篇链表OJ题链接：【链表OJ题(五)】合并两个有序链表链表OJ题(

📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

文章目录

链表OJ题(六)
- 1. 链表分割
- - 思路一带哨兵位的头结点
  - 思路二不强行加头结点
7.总结：

上一篇链表OJ题链接：【链表OJ题(五)】合并两个有序链表

链表OJ题(六)

1. 链表分割

链接：CM11 链表分割

描述：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路一带哨兵位的头结点

题目要求我们将小于 x 的节点和大于等于 x 的节点分隔，小于 x 的节点在前，大于等于 x 的节点在后，且不能改变原来的数据顺序。

不能改变顺序就比较棘手，如果没有这个条件，我们可以用双指针来写。但是题目既然给出了要求，我们就得想办法解决。

我们创建一个新链表存放小于 x 的值，另一个存放大于等于 x 的值。然后遍历原链表，将符合条件的值放入对应的链表中，最后再将存放小于 x 的值的链表和存放大于等于 x 的值的链表链接起来。

那么这过程肯定是尾插，本题使用哨兵位是十分合适的，因为本题有很多的空指针处理的情况，所以我们设定两个哨兵位 lessHead 、 greaterHead。

再给定两个尾lessTail 、 greaterTail，用来尾插。但是最后记得释放哨兵位。

注意如果以 greaterHead 结束的元素不是链表的最后一个元素(即原链表最后一个元素小于 x )，就可能会造成 链表带环 的情况,因为尾插改变前一个链接关系，没有改变自己的后一个链接关系，所以需要断开环，然后将 greaterTail 的 next 置为空。

代码：


class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode* lessTail, *lessHead, *greaterTail, *greaterHead;
        // 建立哨兵位
        lessTail = lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterTail = greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                lessTail->next = cur;
                lessTail = cur;
            }
            else
            {
                greaterTail->next = cur;
                greaterTail = cur;
            }
            cur = cur->next;
        }
        // 链接两个链表
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL; // 断开环
// 拷贝节点，释放哨兵位
        struct ListNode* ans = lessHead->next;
        free(lessHead);
        free(greaterHead);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

思路二不强行加头结点

这道题目不用哨兵位也可以做，但是比较考验细节

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode* lessTail, *lessHead, *greaterHead, *greaterTail;
        lessTail = lessHead = greaterHead = greaterTail = NULL;
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                if (lessTail == NULL)
                {
                    // 第一次尾插
                    lessHead = lessTail = cur;
                }
                else
                {
                    
                    lessTail->next = cur;
                    lessTail = lessTail->next;
                }
                cur = cur->next;
            }
            else
            {
                 if (greaterTail == NULL)
                {
                // 第一次尾插
                    greaterHead = greaterTail = cur;
                }
                else
                {
                    greaterTail->next = cur;
                    greaterTail = greaterTail->next;
                }
                cur = cur->next;
            }
        }
        // lessHead 为空，说明原链表为空或链表的值全大于 x
        // 且链表尾部的 next 一定为空
        // 返回 greaterHead
        if (lessHead == NULL)
            return greaterHead;
        // 如果 lessHead 和 greaterHead 都不为空
        // 说明正常分割
        // 将其链接，greaterHead 尾部链空
        if (lessHead != NULL && greaterHead != NULL)
        {
            lessTail->next = greaterHead;
            greaterTail->next = NULL;
        }
        // 无论是正常分割，还是链表的值全小于 x
        // 都是返回 lessHead
        return lessHead;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64