Remove Duplicates from Sorted List

原题链接: http://oj./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

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     public int val;

 *     public ListNode next;

 *     public ListNode(int x) { val = x; }

 * }

 */

public class Solution {

    public ListNode DeleteDuplicates(ListNode head) {

        ListNode dummy=new ListNode(0);

        dummy.next=head;

        head=dummy;

        

        while(head.next!=null&&head.next.next!=null)

        {

            ListNode n1=head.next;

            ListNode n2=n1.next;

            

            if(n1.val == n1.next.val)

            {

                n1.next=n1.next.next;

            }

            else

            {

                head=head.next;

            }

        }

        

        return dummy.next;

    }

}