题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5。

接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {

    }
};

解答

非递归方法

使用三个指针，分别是指向当前结点的前一结点的指针 prev，指向当前结点的指针 curr，指向当前结点的后一结点的指针 latter，为了让第一个节点也有前一结点，定义一个 ListNode head 变量，其 next 值指向第一个结点。

接着从 curr 为第一个结点开始遍历，直到 latter 为 nullptr。

  • 遍历过程中如果 curr 与 latter 的值不同，则 prev, curr, latter 都往后移一个结点；
  • 如果遇到 curr 和 latter 的值相同，就需要再进入一层循环，删除每一个与 curr 值相同的 latter，并将 latter 指向其自身的下一个，直到 latter 与 curr 的值不同或 latter 为 nullptr 则第二层循环结束，并将当前的 curr 结点也删除，然后 curr 指向当前 latter 的结点，prev->next 指向 curr，如果 latter 不为 nullptr 则 latter 指向当前 latter 的下一个结点。
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
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead == nullptr) return pHead;
        ListNode head(0), *temp = nullptr;
        head.next = pHead;
        ListNode *prev = &head, *curr = pHead, *latter = pHead->next;
        while (latter != nullptr) {
            if (curr->val == latter->val) {
                while (latter != nullptr && curr->val == latter->val) {
                    temp = latter;
                    latter = latter->next;
                    delete temp;
                }
                temp = curr;
                curr = latter;
                prev->next = curr;
                delete temp;
                if (latter != nullptr) latter = latter->next;
            } else {
                prev = curr;
                curr = latter;
                latter = latter->next;
            }
        }
        return head.next;
    }
};

递归方法

递归的主要思路是：判断当前结点与下一结点的值是否相同，如果不同则当前结点为不重复的一个结点，然后就是从当前结点指向的下一个结点开始找不重复的结点；如果当前结点与下一结点的值相同，那么就需要找到第一个与当前结点不同的结点，然后从这个结点开始再找不重复的结点。

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
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead == nullptr) return nullptr;
        if (pHead->next == nullptr) return pHead;
        ListNode *node = nullptr;
        if (pHead->val != pHead->next->val) {
            node = pHead;
            node->next = deleteDuplication(node->next);
        } else {
            ListNode *temp = nullptr;
            node = pHead->next;
            while (node != nullptr && pHead->val == node->val) {
                temp = node;
                node = node->next;
                delete temp;
            }
            delete pHead;
            if (node == nullptr) return nullptr;
            // 从第一个与当前结点不同的结点再次开始递归
            node = deleteDuplication(node);
        }
        return node;
    }
};