LeetCode中怎么刪除排序鏈表中的重復元素

題目描述：

給定一個排序鏈表，刪除所有重復的元素，使得每個元素只出現一次。

示例 1:

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

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

思路分析：

這是一個簡單的問題，僅測試你操作列表的結點指針的能力。由于輸入的列表已排序，因此我們可以通過將結點的值與它之后的結點進行比較來確定它是否為重復結點。如果它是重復的，我們更改當前結點的 next 指針，以便它跳過下一個結點并直接指向下一個結點之后的結點。

復雜度分析

時間復雜度：O(n)，因為列表中的每個結點都檢查一次以確定它是否重復，所以總運行時間為 O(n)，其中 n 是列表中的結點數。

空間復雜度：O(1)，沒有使用額外的空間。

Python實現

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 快慢指針
        if not head:
            return None
        fast, slow = head, head
        while fast:
            if fast.val != slow.val:
                slow.next = fast
                slow = slow.next
            fast = fast.next
        slow.next = None
        return head

java實現：

public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.next.val == current.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

另一個版本的實現：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode dummhead=new ListNode(0);
        dummhead.next=head;
        ListNode cur=head;
        ListNode last=head.next;
        while(last!=null){
            if(cur.val==last.val){
                ListNode tmp=null;
                tmp=last.next;
                cur.next=tmp;
                last=tmp;
            }else{
                cur=last;
                last=last.next;
            }
        }
        return dummhead.next;
    }
}