力扣刷题13--分割链表

分手后的思念是犯贱 2023-02-28 04:18 32阅读 0赞

这个题想了很久还是做错了，后来想不出来了还是去看了题解，借鉴了一些优秀的做法加以改造记录在这里，方便自己加深记忆。

**题目**

**编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。**

示例:
    
    输入: head = 3->5->8->5->10->2->1, x = 5
    输出: 3->1->2->10->5->5->8

[力扣出处面试金典][Link 1]

**解析**

新建两个链表，然后将小于`x`和大于等于`x`的元素分别放在两个链表中，然后将两个链表连接起来即可。

**代码**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* partition(ListNode* head, int x) { 
            ListNode *Head = new ListNode(0); //新建一个节点以Head作为开头 
            ListNode *Tail = new ListNode(0); //新建一个节点以Tail作为开头 
            ListNode *h1 = Head, *h2 = Tail;
            while (head) { 
                if (head->val < x) { 
                    h1->next = head;
                    h1 = h1->next;
                } else { 
                    h2->next = head;
                    h2 = h2->next;
                }
                head = head->next;
            }
            h1->next = Tail->next;
            h2->next = nullptr;
            return Head->next;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]

注：一个问题困扰了两天，技能有待加强，学习从未停止！

[Link 1]: https://leetcode-cn.com/problems/partition-list-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]: /images/20230209/edac144f23aa4d64885a580ea5fb0f4f.png