題目描述

給定一個(gè)已排序的單鏈表，去除單鏈表中的重復(fù)元素，只保留一個(gè)重復(fù)的元素，并且返回新的單鏈表。

例如：
給出1->1->2，你的函數(shù)調(diào)用之后必須返回1->2。

輸入

一個(gè)已排序的單鏈表，例如1->1->2。

輸出

返回1->2。

代碼示例

/**
 * 單鏈表的結(jié)構(gòu)定義
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

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

算法演示

擴(kuò)展

去除單鏈表中重復(fù)元素，不保留任何重復(fù)的元素。

例如：
1->1->2->3->3->4，返回2->4

public static ListNode deleteDuplicatesAll(ListNode head)
{
    if (head == null) {
        return head;
    }

    ListNode dummy = new ListNode(Integer.MAX_VALUE); // 頭結(jié)點(diǎn)
    dummy.next = head;
    ListNode prev, cur;
    prev = dummy;
    cur = head;
    while (cur != null) {
        boolean duplicated = false;
        while (cur.next != null && cur.val == cur.next.val) {
            duplicated = true;
            cur = cur.next;
        }
        if (duplicated) { // 刪除重復(fù)的最后一個(gè)元素
            cur = cur.next;
            continue;
        }
        prev.next = cur;
        prev = prev.next;
        cur = cur.next;
    }
    prev.next = cur;
    return dummy.next;
}

參考文章

• remove-duplicates-from-sorted-list