链表Linked List-Remove duplicates from a sorted linked list从排序的链表中删除重复项的5种方法（11）

灰太狼 2023-09-24 20:29 32阅读 0赞

# 1. 问题 #

For example if the linked list is 11->11->11->21->43->43->60 then removeDuplicates() should convert the list to 11->21->43->60.

# 2.解题方法 #

## 1）遍历结点 ##

> 1.定义list为head  
> 2.while循环list不为null,list.next不等于null  
> 3.如果list的值和list.next的值相等，直接跳过list.next,list.next = list.next.next;  
> 4.如果list的值和list.next的值不相等，list等于list.next，查询list.next的下一个元素，并复制list也是head  
> 5.返回head

`时间复杂度：O(n)，其中 n 是给定链表中的节点数。 辅助空间：O(1)，因为没有使用额外的空间。`

ListNode deleteDuplicates(ListNode head) {
        
           ListNode list = head;
           while (list != null && list.next != null) {
        
               if (list.val == list.next.val) {
        
                   list.next = list.next.next;
               } 
               list = list.next;
           }
           head = list;
           return head;
       }

package com.amy;
    
    public class LinkedList {
        
        static ListNode head;
       static ListNode deleteDuplicates(ListNode head) {
        
           ListNode list = head;
           while (list != null && list.next != null) {
        
               if (list.val == list.next.val) {
        
                   list.next = list.next.next;
               } 
               list = list.next;
           }
           head = list;
           return head;
       }
    
    
        static void printList(ListNode head){
        
            while (head != null) {
        
                System.out.print(head.val + " ");
                head= head.next;
            }
        }
    
        public static void main(String[] args)
        {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(1);
            list.head.next.next = new ListNode(2);
            list.head.next.next.next = new ListNode(3);
            list.head.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next.next
                    = new ListNode(5);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
    
            list.deleteDuplicates(head);
            System.out.println("\n");
            System.out.println(
                    "Linked List after: ");
            list.printList(head);
        }
    
    }
        class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d)
            {
        
                val = d;
                next = null;
            }
        }

Linked List before : 
    1 1 2 3 4 4 5 
    
    Linked List after: 
    1 2 3 4 5

## 2)递归 ##

`时间复杂度：O(n)，其中 n 是给定链表中的节点数。 辅助空间：O(n)`

static ListNode deleteDuplicates(ListNode head) {
        
           if (head == null || head.next == null) {
        
               return head;
           }else{
        
               deleteDuplicates(head.next);
               if (head.val==head.next.val) head.next = head.next.next;
           }
           return head;
       }

package com.amy;
    
    public class LinkedList {
        
        static ListNode head;
       static ListNode deleteDuplicates(ListNode head) {
        
           if ((head == null) || head.next == null) {
        
               return head;
           }else{
        
               deleteDuplicates(head.next);
               if (head.val==head.next.val) head.next = head.next.next;
           }
           return head;
       }
    
    
        static void printList(ListNode head){
        
            while (head != null) {
        
                System.out.print(head.val + " ");
                head= head.next;
            }
        }
    
        public static void main(String[] args)
        {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(1);
            list.head.next.next = new ListNode(2);
            list.head.next.next.next = new ListNode(3);
            list.head.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next.next
                    = new ListNode(5);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
    
            list.deleteDuplicates(head);
            System.out.println("\n");
            System.out.println(
                    "Linked List after: ");
            list.printList(head);
        }
    
    }
        class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d)
            {
        
                val = d;
                next = null;
            }
        }

Linked List before : 
    1 1 2 3 4 4 5 
    
    Linked List after: 
    1 2 3 4 5

## 3)双指针 ##

时间复杂度：O(n)，其中 n 是给定链表中的节点数。 辅助空间：O(1)

static ListNode deleteDuplicates(ListNode head) {
        
           if (head == null|| head.next == null) return head;
           ListNode pre=head,cur=head.next;
           while(cur!=null){
        
               if(cur.val==pre.val){
        
                   pre.next=cur.next;
                   cur=cur.next;
               }else {
        
                   pre=pre.next;
                   cur=pre.next;
               }
           }
           return head;
       }

package com.amy;
    
    import java.util.List;
    
    public class LinkedList {
        
        static ListNode head;
       static ListNode deleteDuplicates(ListNode head) {
        
           if (head == null|| head.next == null) return head;
           ListNode pre=head,cur=head.next;
           while(cur!=null){
        
               if(cur.val==pre.val){
        
                   pre.next=cur.next;
                   cur=cur.next;
               }else {
        
                   pre=pre.next;
                   cur=pre.next;
               }
           }
           return head;
       }
    
    
        static void printList(ListNode head){
        
            while (head != null) {
        
                System.out.print(head.val + " ");
                head= head.next;
            }
        }
    
        public static void main(String[] args)
        {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(1);
            list.head.next.next = new ListNode(2);
            list.head.next.next.next = new ListNode(3);
            list.head.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next.next
                    = new ListNode(5);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
    
            list.deleteDuplicates(head);
            System.out.println("\n");
            System.out.println(
                    "Linked List after: ");
            list.printList(head);
        }
    
    }
        class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d)
            {
        
                val = d;
                next = null;
            }
        }

Linked List before : 
    1 1 2 3 4 4 5 
    
    Linked List after: 
    1 2 3 4 5

## 4)使用map ##

`时间复杂度：O(n)，其中 n 是给定链表中的节点数。 辅助空间：O(n)`

static void deleteDuplicates(ListNode head) {
        
           ListNode list =head;
    
           HashMap<Integer, Boolean> map= new HashMap<>();
            while(list!=null&& list.next!=null) {
        
                if(!map.containsKey(list.val)){
        
                    System.out.print(list.val+" ");
                }
                map.put(list.val,true);
                list=list.next;
            }
       }

package com.amy;
    
    import jakarta.persistence.criteria.CriteriaBuilder;
    
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    
    public class LinkedList {
        
        static ListNode head;
       static void deleteDuplicates(ListNode head) {
        
           ListNode list =head;
    
           HashMap<Integer, Boolean> map= new HashMap<>();
            while(list!=null&& list.next!=null) {
        
                if(!map.containsKey(list.val)){
        
                    System.out.print(list.val+" ");
                }
                map.put(list.val,true);
                list=list.next;
            }
       }
    
    
        static void printList(ListNode head){
        
            while (head != null) {
        
                System.out.print(head.val + " ");
                head= head.next;
            }
        }
    
        public static void main(String[] args)
        {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(1);
            list.head.next.next = new ListNode(2);
            list.head.next.next.next = new ListNode(3);
            list.head.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next.next
                    = new ListNode(5);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
            System.out.println("\n");
    
            list.deleteDuplicates(head);
        }
    
    }
        class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d)
            {
        
                val = d;
                next = null;
            }
        }

Linked List before : 
    1 1 2 3 4 4 5 
    
    1 2 3 4

## 5)使用 Set ##

`时间复杂度：O(n)，其中n是链表中的节点数。这是因为我们遍历链表一次，由于底层平衡二叉搜索树数据结构，每次检查集合和插入集合的操作平均花费 O(logn) 时间。 辅助空间：O(n)，其中 n 是链表中唯一值的数量。这是因为我们使用集合来存储唯一值，它占用 O(n) 空间。`

static ListNode deleteDuplicates(ListNode head) {
        
           //简单来说是利用了set去掉重复元素，利用双指针查询head中重复元素
             if (head == null|| head.next == null) return head;
             ListNode pre =head,cur=head.next;
             HashSet<Integer> set = new HashSet<>();
             set.add(head.val);//增加第一个元素
    
             while(cur!=null&& cur.next!=null) {
        
                 if (set.contains(cur.val)) {
        
                     pre.next = cur.next;
                 } else {
        
                     set.add(cur.val);
                     pre = cur;
                 }
                 cur = cur.next;
             }
    
             return head;
       }

package com.amy;
    
    import jakarta.persistence.criteria.CriteriaBuilder;
    
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    
    public class LinkedList {
        
        static ListNode head;
       static ListNode deleteDuplicates(ListNode head) {
        
           //简单来说是利用了set去掉重复元素，利用双指针查询head中重复元素
             if (head == null|| head.next == null) return head;
             ListNode pre =head,cur=head.next;
             HashSet<Integer> set = new HashSet<>();
             set.add(head.val);//增加第一个元素
    
             while(cur!=null&& cur.next!=null) {
        
                 if (set.contains(cur.val)) {
        
                     pre.next = cur.next;
                 } else {
        
                     set.add(cur.val);
                     pre = cur;
                 }
                 cur = cur.next;
             }
    
             return head;
       }
    
    
        static void printList(ListNode head){
        
            while (head != null) {
        
                System.out.print(head.val + " ");
                head= head.next;
            }
        }
    
        public static void main(String[] args)
        {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(1);
            list.head.next.next = new ListNode(2);
            list.head.next.next.next = new ListNode(3);
            list.head.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next = new ListNode(4);
            list.head.next.next.next.next.next.next
                    = new ListNode(5);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
            System.out.println("\n");
    
            System.out.println(
                    "Linked List after: ");
    
            list.deleteDuplicates(head);
    
            list.printList(head);
        }
    
    }
        class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d)
            {
        
                val = d;
                next = null;
            }
        }

Linked List before : 
    1 1 2 3 4 4 5 
    
    Linked List after: 
    1 2 3 4 5