lc面试准备：Remove Duplicates from Sorted List

1 题目

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.

接口

ListNode deleteDuplicates(ListNode head)

简单的链表操作的题目，要求是删去有序链表中重复的元素。

2 思路

经典的双指针问题，用两个指针一前一后指向链表。维护两个指针，一个指向当前不重复的最后一个元素，一个进行依次扫描，遇到不重复的则更新第一个指针，继续扫描，否则就把前面指针指向当前元素的下一个（即把当前元素从链表中删除）。

复杂度

Time: O(n)

Space: O(1)

3 代码

     public ListNode deleteDuplicates(ListNode head) {
         ListNode dummy = new ListNode(Integer.MAX_VALUE);
         ListNode tail = dummy;
         ListNode pCur = head;
         while(pCur != null){
             if(tail.val != pCur.val){
                 tail.next = pCur;
                 tail = pCur;
             }
             pCur = pCur.next;
         }
         tail.next = null;
         return dummy.next;
     }

4 总结

• 和从数组中移除重复元素那一题一样的思想。
• 链表的操作在面试中考察不多。

5 扩展

Remove Duplicates from Sorted List II

6 参考

1. leetcode
2. Code Ganker征服代码
3. JustDoIT
4. 爱做饭的小莹子