LeetCode 82. 删除排序链表中的重复元素 II

一、题目

1、题目描述

给定一个已排序的链表的头?head?，?删除原始链表中所有重复数字的节点，只留下不同的数字?。返回?已排序的链表?。

2、接口描述

?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

    }
};

3、原题链接

82. 删除排序链表中的重复元素 II

---

二、解题报告

1、思路分析

前驱节点pos，在pos -> next && pos -> next -> next的前提下

令nxt =?pos -> next -> next ， val =?pos -> next -> val

如果nxt和val不重，那么就跳过，pos移动到下一位

否则，nxt移动到第一个和val不重或者为空的位置，断开重复元素

2、复杂度

时间复杂度： O(N)空间复杂度：O(1)

3、代码详解

?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* dummy = new ListNode(0 , nullptr);
    ~Solution(){delete dummy;}
    ListNode* deleteDuplicates(ListNode* head) {
        dummy -> next = head;
        ListNode* pos = dummy , *nxt = nullptr;
        while(pos -> next && pos -> next -> next)
        {
            int val = pos -> next -> val;
            nxt = pos -> next -> next;
            if(nxt -> val != val) {pos = pos -> next ; continue;}
            while(nxt && nxt -> val == val)
                nxt = nxt -> next;
            pos -> next = nxt;
        }
        return dummy -> next;
    }
};