链表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;
    }
};

在这里插入图片描述

思路二不强行加头结点

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

/*
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;
    }
};