Leetcode 83. delete duplicate elements in the sorting linked list

Power button | 83. Delete duplicate elements from the sort list

Title screenshot

 

Method 1 ： One traverse （ Single pointer ）

Because the linked list has been sorted , It can be traversed at one time , Directly remove each element of the linked list from the previous elements .

utilize cur The pointer points to the head node , Then start traversing , If cur And cur.next The corresponding elements are the same , let cur.next Point to cur.next.next, You can delete this node . After traversal, return to the header node .

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

Complete test code

# 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()

Method 2 ： recursive

Regard the linked list as a head node with a short linked list hanging behind it . The linked list can be seen as a head node hanging another shorter linked list , And so on .

Deal with it in the following way ：

1. Delete a short list All repetitions The elements of ;
2. Judge whether the value of the head node of the original linked list is equal to that of the first 1 The value of the shorter chain header node after step processing ;
3. If equal , Then return a shorter linked list ;
4. otherwise , Hang a short linked list behind the head node of the original linked list , Back again .

for example ：1->2->2->3->3->4->5

From back to front

The last linked list is 5

take 5 Hang on 4 On ：4->5

No repetition , Hang it directly on 3 On ：3->4->5

345 No repetition , Then hang it in the front 3 On ：3->3->4->5

Two 3 repeated , After deletion ：4->5

3 and 4 It's not equal , Hang the new short linked list on the original head node 3 On ：3->4->5

At this time “3” It's the second to last “3”, The last one “3” It has been deleted .

And so on , You can delete the penultimate “2” obtain ：2->3->4->5

Finally get ：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

Method 3 ： Double pointer （ Speed pointer ）

Use two pointers to control .

The condition is set to the head node and the next one of the head nodes is non empty . If there is no linked list or the linked list is directly an element , Then return directly .

When there are more than two elements ： The linked list uses two pointers to judge , If the element value pointed by the slow pointer and the fast pointer are different , Then the speed pointer continues to point to the next node , If the same , The slow pointer points to the next node of the fast pointer , That is, the node currently pointed to by the fast pointer is deleted . Then the fast pointer continues to move by itself , repeat , Until the fast pointer points to the end of the linked list .

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

Method four ： Set dummy node

The previous method is to judge the special situation （ The linked list is empty or has only one node ）, It can be eliminated by setting dummy nodes .

That is to add a virtual head node in front of the original linked list .

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