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.

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
  public ListNode deleteDuplicates(ListNode head) {
  }
}

This problem is selected from LeetCode.

Solution

Setup two pointers, diff and itr. Initially both pointers point to the head. itr traverses the list. When the values of the two pointers are different, link diff.next to itr and move diff to itr.

public class Solution {
  public ListNode deleteDuplicates(ListNode head) {
    if(head == null || head.next == null)
      return head;
    
    ListNode diff = head;
    ListNode itr = head.next;
    
    while(itr != null) {
      if(itr.val != diff.val) {
        diff.next = itr;
        diff = itr;
      }
      
      itr = itr.next;
    }
    
    diff.next = null;
    
    return head;
  }
}

RelatedPost