删除有序链表中重复的元素(二)

发表于

描述
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

例如:
给出的链表1→1→1→2→2→4，返回4。
给出的链表1→1→1→2→3，返回2→3。

数据范围： 链表长度满足0≤n≤10000，链表中任意节点的值满足|val|≤1000
要求： 空间复杂度O(n)，时间复杂度O(n)
进阶： 空间复杂度O(1)，时间复杂度O(n)

示例1

1
2
输入:  {1,2,2}
返回:  {1}

示例2

1
2
输入:  {}
返回:  {}

题解

  • 给链表前加上表头，方便可能的话删除第一个节点
  • 遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去
  • 在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点
  • 返回时去掉添加的表头
删除有序链表中重复的元素(2).gif 
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
package main

type ListNode struct{
    Val int
    Next *ListNode
}

/**
  * 
  * @param head ListNode类 
  * @return ListNode类
*/
func deleteDuplicates( head *ListNode ) *ListNode {
    // write code here
    if head == nil || head.Next == nil {
        return head
    }

    dummy := &ListNode{Next: head}
    pre := dummy

    for pre.Next != nil && pre.Next.Next != nil {
        if pre.Next.Val == pre.Next.Next.Val {
            x := pre.Next.Val
            for pre.Next != nil && pre.Next.Val == x {
                pre.Next = pre.Next.Next
            }
        } else {
            pre = pre.Next
        }
    }

    return dummy.Next
}