20.1.3 86. 分隔链表

题目

给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入:head = 1->4->3->2->5->2, x = 3
输出:1->2->2->4->3->5

思路

  1. 思路很简单,双指针,两个伪头部节点,把小于x的串起来,大于等于x的穿起来,两个合并即可
  2. 虽然我也没跑出来。。。之前做过一次也没跑出来,忘了把p2->next设空

代码

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummyHead1 = new ListNode(-1);
        ListNode* dummyHead2 = new ListNode(-1);
        ListNode* p1 = dummyHead1, *p2 = dummyHead2, *curr = head;
        while(curr){
            if(curr->val < x) {
                p1->next = curr;
                p1 = p1->next;
            }
            else {
                p2->next = curr;
                p2 = p2->next;
            }
            curr = curr->next;
        }
        p2->next = nullptr;
        p1->next = dummyHead2->next;

        return dummyHead1->next;
    }
};
上一篇:HDU 1711 - Number Sequence - [KMP模板题]


下一篇:KL散度学习笔记