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

题目描述

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

例如：

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

输入

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

输出

返回1->2。

代码示例

/**

* 单链表的结构定义

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) { val = x; }

* }

*/

publicstaticListNode deleteDuplicates(ListNode head)

{

if(head ==null) {

returnnull;

}

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

publicstaticListNode deleteDuplicatesAll(ListNode head)

{

if(head ==null) {

return head;

}

ListNode dummy =newListNode(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;

}

这一道题目和昨天分享的“去除已排序数组中的重复元素”有点类似，不过对于链表的处理方式和数组不一样，解答这道题大家需要 熟悉链表的一些操作。