Leetcode: 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.

Understand the problem:

The question asks for removing duplicates in a linked list.

For example, 1  -> 1  -> 2, return 1  -> 2

For the linked list is null or empty, return the empty linked list

For the linked list having only one element, return the original linked list

Note that the question does not require in-place transform. The out-of-place solution is clearly simple: we just create a new linked list without duplicated elements. But can we do it in-place?

Solution:

Use two pointers, p and q, q is ahead of p at beginning. Compare the value of p and q, if different, move both p and q, else move the q pointer until they are different again. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        
        ListNode p = head;
        ListNode q = head.next;
        
        while (q != null) {
            if (p.val != q.val) {
                p = p.next;
                q = q.next;
            } else {
                p.next = q.next;
                q = q.next;
            }
        }
        return head;
    }
}

Summary:
The problem is very straight-forward, but be very careful to handle the null-pointer well when moving the pointer.