【牛客网】链表分割

喜欢ヅ旅行 2023-07-03 14:29 22阅读 0赞

## 题目描述 ##

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。  
给定一个链表的头指针 ListNode\* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

## 解题思路 ##

设置两个链表，将小于x的结点放在一个链表中，大于等于x的结点放在另一个链表中，然后合并两个链表。

## 完整代码 ##

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/
    class Partition { 
    public:
        ListNode* partition(ListNode* pHead, int x) { 
            if(pHead == NULL || pHead->next == NULL)
                return pHead;
            ListNode* cur = pHead;
            //设置两个链表
            ListNode* SmallHead = new ListNode(-1);
            ListNode* LargeHead = new ListNode(-1);
            分别设置头指针指向两个链表的首节点
            ListNode* Small = SmallHead;
            ListNode* Large = LargeHead;
            while(cur)
            { 
                //将小于x的结点放在SmallHead链表中
                if(cur->val < x)
                { 
                    Small->next = new ListNode(cur->val);
                    Small = Small->next;
                }
                //将大于等于x的结点放在LargeHead链表中
                else
                { 
                    Large->next = new ListNode(cur->val);
                    Large = Large->next;
                }
                cur = cur->next;
            }
            //将两个链表合并
            //SmallHead链表最后一个节点指向Large的头指针，即LargeHead
            Small->next = LargeHead->next;
            //Large链表最后一个节点设置为尾节点，即设置为null
            Large->next = NULL;
            return SmallHead->next;
        }
    };