This is the 26th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Without buffer, the linked list elements need to be sorted first, and stable sorting algorithm is used to ensure the relative order of equivalent nodes. After sorting, it can be de-processed.

— Leetcode

preface

Hello, everyone. I’m One.

Confused algorithm, rarely confused

Summed up the algorithm brush 12 words truth: persistence, difficult in progress, win in the habit.

Question

Interview question 02.01. Removing duplicate nodes

Difficulty: Easy

Write code to remove duplicate nodes from an unsorted linked list. Keep the original node.

Example 1:

Input: [1, 2, 3, 3, 2, 1] Output: [1, 2, 3]Copy the code

Example 2:

Input: [1, 1, 1, 2] Output: [1, 2]Copy the code

Tip:

The list length is in the range of [0, 20000]. The list elements are in the range [0, 20000]. Advanced:

What if temporary buffers are not allowed?

Solution

General linked list operations, with hash table removal, pay attention to the method of deleting nodes.

head.next=head.next.next;

Code

All LeetCode codes have been synchronized to Github

Welcome to star

/ * * *@authorA coding * /
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode index=head;
        HashSet<Object> set = new HashSet<>();
        set.add(head.val);
        while(head.next! =null) {if (set.add(head.next.val)){
                head=head.next;
            }else {
                head.next=head.next.next;
            };
        }
        head.next=null;
        returnindex; }}Copy the code

Result

Complexity analysis

  • Time complexity: O(N)

Fans of welfare

⭐ today is the 81/100 day to insist on brushing more text

⭐ everyone’s likes, attention, favorites, comments, subscriptions is a creation of the biggest power

⭐ For more data structures and algorithms, please pay attention to the column “Confused Algorithms”.

The last

One foot is difficult to go, one hand is difficult to sing, a person’s power is limited after all, a person’s journey is doomed to be lonely. When you set a good plan, with full of blood ready to set out, must find a partner, and Tang’s monk to the West, the master and his disciples four people united as one to pass the ninety-eight difficult. So,

If you want to learn Java well

Want to go to company

Want to get high salary

Want to have a group of like-minded partners

Please join the technical exchange