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

发表于

描述
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次

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

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

示例1

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

示例2

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

题解

  • 判断链表是否为空链表，空链表不处理直接返回
  • 使用一个指针遍历链表，如果指针当前节点与下一个节点的值相同，我们就跳过下一个节点，当前节点直接连接下个节点的后一位
  • 如果当前节点与下一个节点值不同，继续往后遍历
  • 循环过程中每次用到了两个节点值，要检查连续两个节点是否为空
删除有序链表中重复的元素(1).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
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
    }

    cur := head
    for cur.Next != nil {
        if cur.Val == cur.Next.Val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }

    return head
}