您當前位置：首頁 > php開源 > 綜合技術 > LeetCode筆記：83. Remove Duplicates from Sorted List

LeetCode筆記：83. Remove Duplicates from Sorted List

來源：程序員人生發(fā)布時間：2016-10-04 11:26:10 閱讀次數(shù)：3942次

問題：

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個排好序的鏈表，刪除所有的重復的數(shù)字，讓每一個元素只出現(xiàn)1次。
比如：
給出 1->1->2, 返回1->2.
給出1->1->2->3->3, 返回1->2->3.

思路：

既然鏈表本身已排好序了，那末只用比較當前位置的值和next的值是不是1樣，1樣就把next指向下1個再繼續(xù)判斷就行了，思路還是比較簡單，但是有幾個容易疏忽的點需要注意。

首先是首節(jié)點為空的情況要斟酌；
其次是只有鐺鐺前數(shù)字和下1個數(shù)字不1樣時才把操作的節(jié)點換成下1個節(jié)點去繼續(xù)向后操作，由于有可能有多個重復的數(shù)字串在1起，不能刪除1個節(jié)點后就直接往后移進行判斷，要判斷刪了1個以后下1個是不是還是1樣；
如果鏈表的最后幾個數(shù)字都是重復的，我們在檢測到重復的數(shù)字時會刪除它然后將當前節(jié)點的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;
    }
}