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

来源 leetcode83.删除排序链表中的元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

case1:

1
2

输入：head = [1,1,2]
输出：[1,2,3]

case2:

1
2

输入：head = [1,1,2,3,3]
输出：[1,2,3]

思路

我第一眼的办法比较笨拙，但是很容易想到并且快速写出，天然的想到set去重；然后再从set依次序的取出元素重建链表，并返回链表的头节点；

my ugly code

 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

public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {

        if (head == null) 
            return head;
            
        var list = new List<int>();
        while (head != null)
        {
            list.Add(head.val);
            head = head.next;
        }

        list.Sort();

        HashSet<int> duplicates = new HashSet<int>(list);

        list.Clear();
        list.AddRange(duplicates);

        List<ListNode> listNode = new List<ListNode>();
        list.ForEach(x => listNode.Add(new ListNode(x)));
        for (int i = 0; i < listNode.Count - 1; i++)
        {
            listNode[i].next = listNode[i + 1];
        }
        return listNode[0];
    }
}

虽然AC了，但明显上述代码效率就不高，经历了多次循环，而且相关实现代码重复啰嗦；这主要是没有利用到题目给的“链表是排好序”的特点，那么重复的元素应当在链表中的位置是连续的；

高手思路赏析

解题思路

​ 由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。具体地，我们用指针cur指向链表的头节点，随后开始对链表进行遍历；如果当前cur和cur.next所指向节点的元素相同，那么我们就将cur.next从链表中删除。否则就说明链表中已经不存在其他与cur对应的元素相同的节点，因此可以将cur指向cur.next。

​ 当遍历完整个节点之后，我们返回链表的头节点就好。

细节

当遍历到链表的最后一个节点时，cur.next为空节点，如果不加以判断，访问cur.next对应的元素就会产生运行错误。因此我们只需要遍历到链表的最后一个节点，而不需要遍历完整整个链表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

static ListNode deleteDuplicates(ListNode head)
{
    if (head == null)
    return head;

    var current = head;
    while (current.next != null)
    {
        if (current.val == current.next.val)
        {
            current.next = current.next.next;
        }
        else
        {
            current = current.next;
        }
    }

    return head;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。
  • 空间复杂度：O(1)。

另外给出一个递归版本的简易写法：

  1. 找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return
  2. 想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
  3. 每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        head.next = DeleteDuplicates(head.next);
        if(head.val == head.next.val) head = head.next;
        return head;
    }
}