题目描述

给定一个已排序的单链表，去除单链表中的重复元素，只保留一个重复的元素，并且返回新的单链表。

例如：
给出1->1->2，你的函数调用之后必须返回1->2。

输入

一个已排序的单链表，例如1->1->2。

输出

返回1->2。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 单链表定义
 */
public class ListNode {
    public int val;
    public ListNode next;

    public 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;
}

算法演示

扩展

去除单链表中重复元素，不保留任何重复的元素。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static ListNode deleteDuplicatesAll(ListNode head) {
    if (head == null) {
        return head;
    }

    ListNode dummy = new ListNode(Integer.MAX_VALUE); // 头结点
    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) { // 删除重复的最后一个元素
            cur = cur.next;
            continue;
        }
        prev.next = cur;
        prev = prev.next;
        cur = cur.next;
    }
    prev.next = cur;
    return dummy.next;
}

参考文章