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