83 Remove Duplicates from Sorted List 删除排序链表中的重复元素
Description:
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example:
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
题目描述:
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例:
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
思路:
注意是排序链表, 所以只需要比较下一个结点即可
可以用递归/迭代的方式
时间复杂度O(n), 空间复杂度O(1)
代码:
C++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (!head or !head -> next) return head;
head -> next = deleteDuplicates(head -> next);
if (head -> val == head -> next -> val) head = head -> next;
return head;
}
};
Java:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return head;
ListNode p = head;
while (p.next != null) {
if (p.next.val == p.val) p.next = p.next.next;
else p = p.next;
}
return head;
}
}
Python:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
head.next = self.deleteDuplicates(head.next)
if head.next.val == head.val:
head = head.next
return head
