程序员人生网站导航

LeetCode笔记：83. Remove Duplicates from Sorted List

栏目：综合技术时间：2016-10-04 11:26:10

问题：

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

大意：

给出1个排好序的链表，删除所有的重复的数字，让每一个元素只出现1次。
比如：
给出 1->1->2, 返回1->2.
给出1->1->2->3->3, 返回1->2->3.

思路：

既然链表本身已排好序了，那末只用比较当前位置的值和next的值是不是1样，1样就把next指向下1个再继续判断就行了，思路还是比较简单，但是有几个容易疏忽的点需要注意。

首先是首节点为空的情况要斟酌；
其次是只有铛铛前数字和下1个数字不1样时才把操作的节点换成下1个节点去继续向后操作，由于有可能有多个重复的数字串在1起，不能删除1个节点后就直接往后移进行判断，要判断删了1个以后下1个是不是还是1样；
如果链表的最后几个数字都是重复的，我们在检测到重复的数字时会删除它然后将当前节点的next指向next的next，但是这里要注意判断next是不是还有next，如果没有却进行操作，那就会出错了。

在自己检测时可以试试代码对下面几个测试用例是不是能通过：

[]
[1,1]
[1,1,2]
[1,1,1]

代码（Java）：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode p = head;
        while (p.next != null) {
            ListNode q = p.next;
            if (q.val == p.val) {
                if (q.next != null) {
                    p.next = q.next;
                }
                else p.next = null;
            } 
            else p = p.next;
        }
        return head;
    }
}

------分隔线----------------------------

上一篇 go profile

下一篇 c实现set集合

------分隔线----------------------------