【原题】 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.
【解释】 给定一个已经排序的单链表,要求删除链表当中所有的重复结点。 【思路】 这里最坑的是leetcode上链表并不带有头结点的链表,结果导致要将待删除结点分为头结点和非头结点的判断,增加了很多不必要的操作。 要是有头结点世界该多美好啊! 还傻傻地做了很多判断,看到My accepted Java code的解法,有如醍醐灌顶,没有头结点不会自己造一个??? Mark一下。
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return head;
ListNode fakeHead=new ListNode(0);//新建一个头结点
fakeHead.next=head;
ListNode pre=fakeHead, cur=head;
while(cur!=null){
while(cur.next!=null&&cur.val==cur.next.val)
cur=cur.next;
if(pre.next==cur)//相邻元素没有重复
pre=pre.next;
else
pre.next=cur.next;
cur=cur.next;
}
return fakeHead.next;
}
}
除此之外可以使用递归的解法。 参考My Recursive Java Solution
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return head;
if(head.next!=null&&head.next.val==head.val){
while(head.next!=null&&head.next.val==head.val)//循环直到找到一个不重复的node
head=head.next;
return deleteDuplicates(head.next);
}
else head.next=deleteDuplicates(head.next);//相邻无重复
return head;
}
}