83.82.Remove Duplicates from Sorted List I/II (recur)

83.82. Remove Duplicates from Sorted List(Recur)
easy/ medium

83. https://leetcode.com/problems/remove-duplicates-from-sorted-list/#/description

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.

思路： Two methods, 1. from end to start, skip each dup node (in summary)
           2. in return case, skip dup node & keep calling next deleteDup function

Complexity: Time O(n) Space O(1)

public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)return head;
        if(head.val == head.next.val){
            while(head.next != null && head.val == head.next.val){
                head = head.next;
            }
            //think it as return head.next, so we retain one dup node
            return deleteDuplicates(head);
            //once return, will perform code after the below recursive call, so we call recursive again here
        }
        head.next = deleteDuplicates(head.next);
        return head;
    }

82. https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/#/description

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.

 思路： Use recursion, in return case, skip dup node & keep calling next deleteDup function

Complexity: Time O(n) Space O(1)

public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)return head;
        if(head.val == head.next.val){
            while(head.next != null && head.val == head.next.val){
                head = head.next;
            }
            //think it as return head.next, so we skip the dup one
            return deleteDuplicates(head.next);
            //once return, will perform code after the below recursive call, so we call recursive again here
        }
        head.next = deleteDuplicates(head.next);
        return head;
    }