Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only

*distinct*numbers from the original list.
For example,

Given

Given

Given

`1->2->3->3->4->4->5`

, return `1->2->5`

.Given

`1->1->1->2->3`

, return `2->3`

.**Understand the problem:**

The problem asks for removing duplicated numbers from a linked list. Note the the difference from the last post is all duplicated numbers are deleted. For example,

1 -> 1 -> 1 -> 2 , return 2

For an empty linked list, return null

For a linked list with only 1 element, return the original linked list.

**Solution:**

We still use two pointers, p and q. q pointer is one step ahead of p at beginning. Move q pointer if q is duplicated. If q pointer moves more than one steps (has duplicates), move p.next = q.next. Else, move p and q one step ahead. The crux is to determine if q moves multiple steps. If yes, it means q pointer has duplicates, we should jump the q pointer. Else, q pointer should be saved. For example,

0 -> 1 -> 2 ->3, where p and q points to 0 and 1, respectively. Since 1 has no duplicates afterwards, we move both p and q one step ahead.

0 -> 1 -> 1 -> 2 -> 3, where again p and q points to 0 and 1, respectively. Since now i has duplicates afterwards, we should jump the 1s and points p to the value of 2.

**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 || head.next == null) return head; ListNode helper = new ListNode(0); helper.next = head; head = helper; ListNode p = head; ListNode q = head.next; while (q != null) { while (q.next != null && q.val == q.next.val) { q = q.next; } if (p.next != q) { p.next = q.next; if (q != null) q = q.next; } else { p = p.next; q = q.next; } } return head.next; } }

**Discussion:**

Note that we used a helper node ahead of the head node. This is to avoid the complexities in deleting the head node, which may be the case for this question. Using helper node is a common usage when updating the head node.

**Updates on 10/7/14:**

/** * 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 || head.next == null) { return head; } ListNode dummyNode = new ListNode(Integer.MIN_VALUE); dummyNode.next = head; ListNode prev = dummyNode; ListNode curr = head; while (curr != null && curr.next != null) { ListNode next = curr.next; if (curr.val == next.val) { while (curr.next != null && curr.val == next.val) { curr = curr.next; next = next.next; } prev.next = next; curr = next; } else { prev = prev.next; curr = curr.next; } } return dummyNode.next; } }

## No comments:

## Post a Comment