题目:
leetcode 83.Remove Duplicates from Sorted List (Easy)
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
题目大意：
将有序链表中的所有重复元素删除，使得每个元素只出现一次。
解题思路：
也是两种思路，iteratively和recursively;
iteratively: 结点和自己的后继节点的数值比较，重复就将后继指针指向原来后继的后继，否则指针后移；
recursively: 将原链表看作最后2个节点和前面的链表、最后3个结点和前面的链表，以此类推，图示和leetcode 21合并有序链表的递归算法类似。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24Java:
iteratively:
public ListNode deleteDuplicates(ListNode head){
if(head == null || head.next == null) return head;
ListNode cur = head;
while(cur != null && cur.next != null){//这块儿也可以写成while(cur.next != null)
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
recursively:
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;
}
Python:
