Blog Details

Remove Duplicates from sorted LinkedList

1. Description

Give a list of ascending numbers, delete all duplicated numbers from the list.

Input:[1,1,2,2,3,3,,5,5,5,7,8,8]
Output: [1,2,3,5,7,8]

The List is represented as below in Java:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

2. Solution

This problem is relative easy. To solve it, you can compare the current node with next node, if they have same value, skip it. Otherwise add it the new node. You will only need O(n) time complexity and O(1) space complexity.

Source code

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