思路

题目分析

  1. 题目给出了一个链表，链表中元素有序排序
  2. 我们要将链表中相邻重复的元素都删去，返回剩下部分的链表头结点
  • 迭代
    • 为了代码简便，我们引入哑结点dummyNode，以便处理头结点的问题
    • 我们选用三个指针，分别指向三个相邻的位置
    • 后两个指针进行对结点是否有相同值进行判断，并引入temp指针来删去重复元素
    • 第一个指针的next成员可以接到后两个指针找到的结点值不同的位置
    • 以上部分循环迭代即可
  • 递归
    • 我们明确递归函数的定义为返回以当前结点为首的不含重复元素的链表
    • 因此首先递归终止条件为当前结点是否为空、当前结点下一节点是否为空，进行判断返回
    • 需要进行递归的情况如下
      • pHead->val != pHead->next->val 因此相邻结点的值不同，所以只需要继续递归调用pHead->next = deleteDuplication(pHead->next)即可，最终返回pHead
      • pHead->val == pHead->next->val 因此相邻结点值相同，我们引入newPoint指针，找到当前表中第一个不重复元素的结点作为newPoint，因此直接返回deleteDuplication(newPoint)

方法一：迭代

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead == NULL || pHead->next == NULL) return pHead;
        ListNode* dummyNode = new ListNode(-200);    // 给首节点前面加一个dummy结点便于代码整理
        dummyNode->next = pHead;
        ListNode* p = dummyNode;                     // 用三指针标记相邻的三个结点
        ListNode* q = p->next;
        ListNode* r = q->next;
        
        while(r != NULL) {
            if(q->val != r->val) {                   // 如果没有出现相邻的结点值相同，则直接往后迭代
                p = p->next;
                q = q->next;
                r = r->next;
            }
            else {
                ListNode * temp;
                while(r != NULL && q->val == r->val) {    // 否则对后面两个指针一直迭代直到两个相邻结点值不同为止
                    temp = q;
                    q = q->next;
                    r = r->next;
                    delete(temp);
                }
                temp = q;
                q = q->next;
                if(r != NULL) r = r->next;                // 更新最终的结点位置
                delete(temp);                             // 删除重复结点
                p->next = q;                              // 将前面的指针接回来
            }
        }
        return dummyNode->next;
    }
};

复杂度分析

  • 时间复杂度：O(N)O(N)，全程只是顺序遍历了所有节点一次
  • 空间复杂度：O(1)O(1)，引入了一个额外的dummyNode结点

方法二：递归

alt

/*
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;                // 边界条件判断：本身为空或下一个节点为空
        if(pHead->val != pHead->next->val) {                    // 如果相邻的两节点值不相同，则递归下一个结点
            pHead->next = deleteDuplication(pHead->next);
        }
        else{
            ListNode* newPoint = pHead->next;
            while(newPoint && pHead->val == newPoint->val) {    // 如果相邻结点值相同，则迭代找到第一个不同的位置
                newPoint = newPoint->next;
            }
            return deleteDuplication(newPoint);                 // 返回第一个不同值的结点
        }
        return pHead;                                           // 返回pHead本身
    }
};

复杂度分析

  • 时间复杂度：O(N)O(N)，全程只是顺序遍历了所有节点一次
  • 空间复杂度：O(N)O(N)，递归栈的空间使用