题目:
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例:
输入: 1->1->2
输出: 1->2
输入: 1->1->2->3->3
输出: 1->2->3
分析:
因为是有序的链表,所以好处理的多,因为如果某个元素含有重复的,当这个元素第一次出现的时候,其后面若干位置一定是和值一样的元素,那么我们就可以以此为判断,直接进行删除操作,然后继续遍历,后面的元素是否和当前的元素值相同,相同的话继续改变当前元素的next指针的指向,直到碰见值不相同的元素。
代码:
public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null){ return head; } ListNode p = head; while (p.next != null ){ if (p.val == p.next.val){ p.next = p.next.next; }else { p = p.next; } } return head; }
解法二:递归
public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; head.next = deleteDuplicates(head.next); return head.val == head.next.val ? head.next : head;