JZ56 删除链表中重复的结点

本文最后更新于：2022年4月9日 中午

image-20211010152911308

Solution

  • 借助栈
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
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead || !pHead->next) return pHead;
        stack<ListNode *> stack;
        ListNode *cur = pHead;
        int pre = cur->val - 1;    // 确保头结点入栈
        
        while (cur) {
            if (cur->val != pre) {
                stack.push(cur);
                pre = cur->val;
            } else {
                if (!stack.empty() && stack.top()->val == cur->val) {
                    stack.pop();
                }
            }
            cur = cur->next;
        }
        
        ListNode *node = nullptr;    // 头插法构造链表
        while (!stack.empty()) {
            ListNode *tmp = stack.top();
            tmp->next = node;
            node = tmp;
            stack.pop();
        }
        return node;
    }
};
  • 原地操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead || !pHead->next) return pHead;
        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = pHead;
        ListNode* pre = dummyHead, *cur = pHead;
        while (cur) {
            int num = 0;
            int curVal = cur->val; // 关键点 1
            while (cur && cur->val == curVal) {
                cur = cur->next;
                num += 1;
            }
            if (num > 1) // 关键点 2
                pre->next = cur;
            else         // 关键点 3
                pre = pre->next;
        }
        return dummyHead->next;
    }
};