83.md

83. 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.

Thinking Process

1. Use two pointers, one points to the current node, one points to the next node that has different values from the current node.
2. Update two pointers accordingly as we scan through the list

Code

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

Complexity

1. Space complexity is O(1) as no additional data structure is needed
2. Time complexity is O(n) as the list will be scanned exactly once (even there're nested while loops)