83 Remove Duplicates from Sorted List 刪除排序鏈表中的重復(fù)元素

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

題目描述:
給定一個(gè)排序鏈表，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。

示例:

示例 1:
輸入: 1->1->2
輸出: 1->2

示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3

思路:

注意是排序鏈表, 所以只需要比較下一個(gè)結(jié)點(diǎn)即可
可以用遞歸/迭代的方式
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度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