LeetCode - Easy - 83. Remove Duplicates from Sorted List

雨点打透心脏的1/2处 2022-12-28 00:47 110阅读 0赞

## Topic ##

Linked List, Two Pointers

## Description ##

[https://leetcode.com/problems/remove-duplicates-from-sorted-list/][https_leetcode.com_problems_remove-duplicates-from-sorted-list]

Given a sorted linked list, delete all duplicates such that each element appear only once.

**Example 1**:

Input: 1->1->2
    Output: 1->2

**Example 2**:

Input: 1->1->2->3->3
    Output: 1->2->3

## Analysis ##

方法一：逐个扫描，重复节点的逐个移除

方法二：将不重复的值，替换重复的值

方法三：递归法。方法一、二是从链头开始的，而本法从**链尾**开始。

## Submission ##

import com.lun.util.SinglyLinkedList.ListNode;
    
    public class RemoveDuplicatesFromSortedList { 
    	
    	//方法一：逐个扫描，重复的逐个删除
        public ListNode deleteDuplicates1(ListNode head) { 
        	if(head == null) return head;
        	
            ListNode prev = head, curr = head.next;
            
            while(curr != null) { 
            	if(curr.val == prev.val) { 
            		prev.next = curr.next;
            		curr.next = null;//垃圾回收
            		curr = prev.next;
            	}else { 
            		prev = curr;
            		curr = curr.next;
            	}
            }
            
            return head;
        }
        
        
        //方法二：将不重复的值，替换重复的值
        public ListNode deleteDuplicates2(ListNode head) { 
        	if(head == null) return head;
            ListNode p1 = head, p2 = head.next;
            
            while (p2 != null) { 
            	if(p1.val != p2.val) { 
            		p1.next.val = p2.val;
            		p1 = p1.next;
            	}
            	p2 = p2.next;
            }
            
        	p1.next = null;//垃圾回收
        	return head;
        }
        
        //方法三：递归法
        public ListNode deleteDuplicates3(ListNode head) { 
    		if(head == null || head.next == null) return head;
    		
    		head.next = deleteDuplicates3(head.next);
    		
    		ListNode result = null;
    		
    		if(head.val == head.next.val) { 
    			result = head.next;
    			head.next = null;//垃圾回收
    		}else { 
    			result = head;
    		}
    		
    		return result;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.SinglyLinkedList;
    
    public class RemoveDuplicatesFromSortedListTest { 
    
    	@Test
    	public void test() { 
    		RemoveDuplicatesFromSortedList obj = new RemoveDuplicatesFromSortedList();
    
    		int[] array1 = { 1, 1, 2};
    		int[] expected1 = { 1, 2};
    		
    		assertTrue(SinglyLinkedList.equals(SinglyLinkedList.intArray2List(expected1), 
    				obj.deleteDuplicates1(SinglyLinkedList.intArray2List(array1))));
    		assertTrue(SinglyLinkedList.equals(SinglyLinkedList.intArray2List(expected1), 
    				obj.deleteDuplicates2(SinglyLinkedList.intArray2List(array1))));
    		assertTrue(SinglyLinkedList.equals(SinglyLinkedList.intArray2List(expected1), 
    				obj.deleteDuplicates3(SinglyLinkedList.intArray2List(array1))));
    		
    		
    		int[] array2 = { 1, 1, 2, 3, 3};
    		int[] expected2 = { 1, 2, 3};
    		
    		assertTrue(SinglyLinkedList.equals(SinglyLinkedList.intArray2List(expected2), 
    				obj.deleteDuplicates1(SinglyLinkedList.intArray2List(array2))));
    		assertTrue(SinglyLinkedList.equals(SinglyLinkedList.intArray2List(expected2), 
    				obj.deleteDuplicates2(SinglyLinkedList.intArray2List(array2))));
    		assertTrue(SinglyLinkedList.equals(SinglyLinkedList.intArray2List(expected2), 
    				obj.deleteDuplicates3(SinglyLinkedList.intArray2List(array2))));
    		
    		
    	}
    }

[https_leetcode.com_problems_remove-duplicates-from-sorted-list]: https://leetcode.com/problems/remove-duplicates-from-sorted-list/