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 代码

 1     public ListNode deleteDuplicates(ListNode head) {
 2         ListNode dummy = new ListNode(Integer.MAX_VALUE);
 3         ListNode tail = dummy;
 4         ListNode pCur = head;
 5         while(pCur != null){
 6             if(tail.val != pCur.val){
 7                 tail.next = pCur;
 8                 tail = pCur;
 9             }
10             pCur = pCur.next;
11         }
12         tail.next = null;
13         return dummy.next;
14     }

lc面试准备：Remove Duplicates from Sorted List

1 题目

接口

2 思路

复杂度

3 代码

4 总结

5 扩展

6 参考