83. Remove Duplicates

83. Remove Duplicates from Sorted List

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

For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.

My Solutions:

• 新建dummy记录开头

• 如果head 和head.next 相同，跳过head.next

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        
        if (head == null || head.next == null) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        while (head != null && head.next != null) {
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
        
    }
}

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

My Solutions:

多增加把重复节点跳过的部分

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        
        ListNode dummy = new ListNode(0), slow = dummy, fast = head;
        dummy.next = head;
        while(fast != null) {
    	    while (fast.next != null && fast.val == fast.next.val) {
     		    fast = fast.next;    //while loop to find the last node of the dups.
    	    }
    	    if (slow.next != fast) { //duplicates detected.
    		    slow.next = fast.next; //remove the dups.
    	    } else { //no dup, move down both pointer.
    		    slow = slow.next;
    	    }
    	    fast = fast.next; //reposition the fast pointer.
        }
        return dummy.next;
        
    }
}

• recursive

        //recursive
         if (head == null) return null;
    
        // if (head.next != null && head.val == head.next.val) {
        //     while (head.next != null && head.val == head.next.val) {
        //         head = head.next;
        //     }
        //     return deleteDuplicates(head.next);
        // } else {
        //     head.next = deleteDuplicates(head.next);
        // }
        // return head;