Jamzen的技术博客
0%

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

发表于 分类于 Valine：

给一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3

解法：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
object DeleteLinkedListDuplicates {

     def main(args: Array[String]): Unit = {
          println(deleteDuplicates(null))
          println(deleteDuplicates(ListNode(3, null)))
          println(deleteDuplicates(ListNode(3, ListNode(3, null))))
          println(deleteDuplicates(ListNode(2, ListNode(3, null))))
          println(deleteDuplicates(ListNode(1, ListNode(1, ListNode(2, ListNode(3, null))))))
          println(deleteDuplicates(ListNode(1, ListNode(1, ListNode(2, ListNode(3, null))))))
          println(deleteDuplicates(ListNode(1, ListNode(1, ListNode(2, ListNode(3, ListNode(3, null)))))))
     }

     def deleteDuplicates(head: ListNode): ListNode = {
          if (head == null || head.next == null) return head
          val res = ListNode(0, null)
          var resCur = res
          var cur = head
          var curVal = head.x
          var repeat = false
          while (cur.next != null) {
               if (cur.next.x == curVal) {
                    cur = cur.next
                    repeat = true
               } else {
                    if (!repeat) {
                         resCur.next = cur
                         resCur = resCur.next
                         if (cur.next != null) {
                              cur = cur.next
                              curVal = cur.x
                         }
                         resCur.next = null
                    } else {
                         repeat = false
                         if (cur.next != null) {
                              cur = cur.next
                              curVal = cur.x
                         }
                    }
               }
          }

          if (!repeat) {
               resCur.next = cur
               resCur = resCur.next
               resCur.next = null
          }

          res.next
     }

     case class ListNode(x: Int, var next: ListNode)

}