去除已排序链表中的重复元素

2016-09-17 crane-yuan 更多博文 » 博客 » GitHub »

LeetCode algorithm

原文链接 https://crane-yuan.github.io/2016/09/17/Remove-sorted-linkedlist-duplicated-value/
注:以下为加速网络访问所做的原文缓存,经过重新格式化,可能存在格式方面的问题,或偶有遗漏信息,请以原文为准。


题目描述

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

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

输入

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

输出

返回1->2。

代码示例

/** 单链表定义
 *
 * @author: crane-yuan
 * @date: 2016-9-17 下午12:11:13
 */
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;
}

算法演示

<!--more-->

扩展

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

例如: 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); // 头结点
    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;
}

参考文章