Remove Duplicates from Sorted List -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/
这是一道比较简单的链表操作的题目，要求是删去有序链表中重复的元素。方法比较清晰，维护两个指针，一个指向当前不重复的最后一个元素，一个进行依次扫描，遇到不重复的则更新第一个指针，继续扫描，否则就把前面指针指向当前元素的下一个（即把当前元素从链表中删除）。时间上只需要一次扫描，所以是O(n)，空间上两个额外指针，是O(1)。代码如下：

public ListNode deleteDuplicates(ListNode head) {
    if(head == null)
        return head;
    ListNode pre = head;
    ListNode cur = head.next;
    while(cur!=null)
    {
        if(cur.val == pre.val)
            pre.next = cur.next;
        else    
            pre = cur;
        cur = cur.next;
    }
    return head;
}

链表操作在LeetCode中占有一定的比例，不过面试中出现的频率并不是特别高，不过基本的操作还是要熟练的。这道题目还可以求于另一个数据结构数组中，也比较简单，有兴趣可以看看Remove Duplicates from Sorted Array。