LeetCode（Linked List) 83. Remove Duplicates from Sorted List

偏执的太偏执、 2023-09-24 18:55 116阅读 0赞

# 1.问题 #

Given the head of `a sorted linked list`, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

# 2. 解题思路 #

Example 1:

![在这里插入图片描述][87480ef51ca84397814b8199a87b17e6.png]

> Input: head = \[1,1,2\]  
> Output: \[1,2\]

Example 2:

![在这里插入图片描述][f4df87cbfb0f4f68ad08db1167a34edb.png]

> Input: head = \[1,1,2,3,3\]  
> Output: \[1,2,3\]

Constraints:

*  The number of nodes in the list is in the range \[0, 300\].
 *  \-100 <= Node.val <= 100
 *  The list is guaranteed to be sorted in ascending order.

## 方法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

## 方法2： ##

> 双指针

# 3. 代码 #

## 代码1： ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            ListNode list = head;     //1.定义list为head
             while(list!=null&&list.next!=null) {
        //2.while循环list不为null,list.next不等于null
            	 if (list.val == list.next.val) {
        //3.如果list的值和list.next的值相等，直接跳过list.next,list.next = list.next.next;
            		 list.next = list.next.next;
            	 } else {
        //4.如果list的值和list.next的值不相等，list等于list.next，查询list.next的下一个元素，并复制list也是head
            		 list = list.next;
            	 }
             }  
             return head;//5.返回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;
               } else {
        
                   list = list.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： ##

public class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            if(head == null) return null;//1.如果head为null,返回null
            ListNode pre = head;//2.pre为head,cur为 head.next
            ListNode cur = head.next;
            while(cur != null){
        //3.cur也就head.next不为null循环
                if(cur.val == pre.val){
        //如果cur的值和pre的值相等和不相等进行比较
                    pre.next = cur.next;
                    cur = cur.next;
                }
                else{
        
                    pre = pre.next;
                    cur = pre.next;
                }
            }
            return head;//4.返回head
        }
    }

> 解题思路和以上代码相同

public ListNode deleteDuplicates(ListNode head) {
        //双指针
    		if(head==null || head.next==null) return head;
    		ListNode p = head;
    		ListNode curr = p.next;
    		while(curr!=null) {
        
    			if(curr.val!=p.val) {
        
    				p.next=curr;
    				p=curr;
    			}
    			curr=curr.next;
    		}
    		p.next=curr;
    		return head;
    	}

### 本地代码测试 ###

package com.Amy.leecode;
    
    /**
     * @author: Amy
     * @create: 2023-02-15 09:38
     **/
    class LinkedList {
        
    
        static ListNode head;
    
        static class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d)
            {
        
                val = d;
                next = null;
            }
        }
    
        ListNode  deleteDuplicates(ListNode head)//删除重复项的函数 已排序的链表
        {
        
            if(head==null || head.next==null) return head;
            ListNode p = head;
            ListNode curr = p.next;
            while(curr!=null) {
        
                if(curr.val!=p.val) {
        
                    p.next=curr;
                    p=curr;
                }
                curr=curr.next;
            }
            p.next=curr;
            return head;
        }
    
        void printList(ListNode node)
        {
        
            while (node != null) {
        
                System.out.print(node.val + " ");
                node = node.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);
        }
    }

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

[87480ef51ca84397814b8199a87b17e6.png]: https://img-blog.csdnimg.cn/87480ef51ca84397814b8199a87b17e6.png
[f4df87cbfb0f4f68ad08db1167a34edb.png]: https://img-blog.csdnimg.cn/f4df87cbfb0f4f68ad08db1167a34edb.png