This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 83 on LeetCode. Delete the duplicate elements in the sorted list.

Tag: A linked list.

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.

Example 1:

Input: head = [1,2]Copy the code

Example 2:

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

Tip:

  • The number of nodes in the linked list is in the range [0, 300]
  • -100 <= Node.val <= 100
  • The subject data ensures that the linked list is sorted in ascending order

The basic idea

82. Delete duplicate element II from sorted list

  1. Dummy creates a “dummy head node” to reduce boundary judgment, and the list of answers will be followed by dummy

  2. Use tail to represent the end of the currently valid list

  3. A linked list scan is performed using the head pointer from the original input

Code:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        while(head ! =null) {
            // If the value is not equal, ensure that only the first of the same nodes will be added to the answer
            if(tail.val ! = head.val) { tail.next = head; tail = tail.next; } head = head.next; } tail.next =null;
        returndummy.next; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

expand

  • How to implement “delete all duplicate elements”?

Delete duplicate element II from sorted list

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while(head ! =null) {
            // When entering the loop, ensure that the head is not the same as the previous node
            if (head.next == null|| head.val ! = head.next.val) { tail.next = head; tail = tail.next; }// If the head is the same as the next node, skip the same node
            while(head.next ! =null && head.val == head.next.val) head = head.next;
            head = head.next;
        }
        tail.next = null;
        returndummy.next; }}Copy the code

The last

This is the No.83 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks, we will first brush all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.