Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Leetcode83 – Removes duplicate elements from sorted linked lists

above

This article is the rookie brush problem record, only used as notes, not the best solution.

The title information

There is a linked list in ascending order. Given the head node of the linked list, remove all duplicate elements so that each element appears only once.

Returns a linked list of results, also in ascending order.

Head = [1,1,2,3,3]Copy the code

Analysis of the problem

Method 1

This method mainly adopts the idea of recursive processing. Since it is a sorted linked list, all you really need to do is compare the values of consecutive node elements. Therefore, the idea of recursive operation is adopted. Traversal means that if an empty node is encountered, it proves that the traversal of the linked list has been completed and can be directly returned. If the next node of the node is empty, the list is considered to be finished and can be returned directly. If the next node is not empty, the value of the current node is compared to the value of the next node. If they are not equal, no action is required. If the two values are equal, set the next node of the current node to the original next node of the next node, and remove the next node itself. This accomplishes the purpose of duplicate element deletion. This recursively removes all list duplicates. The code is as follows:

public ListNode deleteDuplicates(ListNode head) {
    if(head == null){
        return null;
    }
    if(head.next != null){
        deleteDuplicates(head.next);
        if(head.val == head.next.val){
            head.next = head.next.next;
        }
        return head;
    }else{
        return head;
    }
}
Copy the code

Complexity analysis

  • Time complexity O (n)
  • Space complexity O (1)

Afterword.

  • How many events through the ages? Leisurely. The Yangtze River is still rolling.