LeetCode ＃83. 删除排序链表中的重复元素

力扣 | 83. 删除排序链表中的重复元素

题目截图

 

方法一：一次遍历（单指针）

因为该链表是已经排序好的，可以一次性遍历，直接将链表每个元素与之前元素重复的去掉。

利用cur指针指向头节点，然后开始遍历，如果cur与cur.next对应的元素相同，就让cur.next指向cur.next.next，即可删除该结点。遍历完成后返回头节点即可。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head

        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

完整测试代码

# 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 head

        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

class Linked_list:
    def create_linked_list(self, nums):
        if len(nums) == 0:
            return None
        head = ListNode(nums[0])
        cur = head
        for i in range(1, len(nums)):
            cur.next = ListNode(nums[i])
            cur = cur.next
        return head


    def print_linked_list(self, list_node):
        if list_node is None:
            return

        cur = list_node
        while cur:
            print(cur.val, '->', end=' ')
            cur = cur.next
        print('null')

class main:
    a = Solution()
    list_1 = [1, 1, 2, 3, 3]
    ll = Linked_list()
    h = ll.create_linked_list(list_1)
    b = a.deleteDuplicates(h)
    ll.print_linked_list(b)


if __name__ == '__main__':
    main()

方法二：递归

将链表看成一个头节点后面悬挂着短一截的链表。该链表又可以看成一个头节点悬挂着另一个更短的链表，以此类推。

按照下面的方式处理：

1. 删除短一截链表中所有重复的元素；
2. 判断原链表的头节点的值是否等于经过第 1 步处理后的更短链表头节点的值；
3. 若相等，则返回更短的链表；
4. 否则，将短一截链表挂接在原链表的头节点的后面，再返回。

例如：1->2->2->3->3->4->5

从后往前

最后一个链表为5

将5挂在4上：4->5

无重复，直接再挂在3上：3->4->5

345无重复，再挂在前面的3上：3->3->4->5

两个3重复了，删除后得：4->5

3和4不相等，将这个新得的短一截链表挂在原头节点3上：3->4->5

此时的“3”是倒数第二个“3”，倒数第一个“3”已经被删除。

以此类推，可以删除倒数第一个“2”得到：2->3->4->5

最后得到：1->2->3->4->5

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        head.next = self.deleteDuplicates(head.next)
        return head.next if head.val == head.next.val else head

方法三：双指针（快慢指针）

利用两个指针分别控制。

条件设置为头节点和头节点的下一个为非空。若没有链表或者链表直接一个元素，则直接返回。

当有两个以上的元素时：链表利用快慢两个指针判断，若慢指针与快指针指向的元素值不相同，则快慢指针分别继续指向下一结点，若相同，慢指针指向快指针的下一节点，即快指针当前指向的结点被删除。然后快指针继续自己移动，如此重复，直到快指针指向链表尾部。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        slow = head
        fast = head.next
        while fast:
            if slow.val != fast.val:
                slow = slow.next
            else:
                slow.next = fast.next
            fast = fast.next
        return head

方法四：设置哑结点

前面的方法要判断特殊情况（链表为空或者链表只有一个节点），可以通过设置哑结点的情况消除。

也就是在原链表前再增加一个虚拟的头节点。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummyHead = ListNode(1000, head) 
        cur = dummyHead 
        while cur.next: 
            if cur.next.val == cur.val: 
                cur.next = cur.next.next 
            else: 
                cur = cur.next 
        return dummyHead.next