# 删除链表里面重复的元素-1 ### 1. Link {% embed url="" %} ### 2. 题目描述 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。\ 例如：\ 给出的链表为1 \to 2\to 3\to 3\to 4\to 4\to51→2→3→3→4→4→5, 返回1\to 2\to51→2→5.\ 给出的链表为1\to1 \to 1\to 2 \to 31→1→1→2→3, 返回2\to 32→3.\ \ \ 示例1 ### 输入 复制 ``` {1,2,2} ``` ### 返回值 复制 ``` {1} ``` ### 3. 思路 1. method: two pointer 快慢指针 2. 先创建一个fake head 它的next = head。因为我们可能会删除list的head 3. 用快慢指针方法，slow = fake\_head, fast= head然后检测fast和fast.next是否存在如果存在，再看看它们的值是否一样。 4. 如果fast.val = fast.next.val 那么就以fast为起始点，用一个temp的指针开始往后遍历直到找到重复的sub-list的最后一个node的next node，并把fast = temp， slow\.next = temp 从而跳过duplicate的node 5. 如果fast.val != fast.next.val, 直接把slow， fast都往前移动一位 6. Time: O(n), Space:O(1) ### 4. Coding ``` # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head ListNode类 # @return ListNode类 # class Solution: def deleteDuplicates(self , head ): # write code here #input: head of linked list # output: deduplicated linkedlist # idea: two pointer # 1. slow: store previous node of the first duplicated node # 2. fast store the last duplicated node # 3.so we need fake_node and start from fake node so that we can # easily remove the head node if necessary # 4. iterate the whole list using fast # 5. when we find fast.val == fast.next.val # use temp = fast.next and find the end of the duplicated string # then let slow.next = temp, fast = temp to skip duplicated elements #bsae case: if not head: return head slow = fake_head = ListNode(None) fake_head.next = head fast = head while fast and fast.next: if fast.val == fast.next.val: cur = fast.next while cur and cur.val == fast.val: cur = cur.next slow.next = cur fast = cur else: slow = slow.next fast = fast.next return fake_head.next ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://wenkangwei.gitbook.io/leetcode-notes/datastructure/linkedlist/shan-chu-lian-biao-li-mian-zhong-fu-de-yuan-su.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.