Remove Duplicates from Sorted List

Leave a comment

June 3, 2016 by oneOokay

  • Remove Duplicates from Sorted List
  • Remove LinedList elements
  • Remove Duplicates from Sorted List II

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.


head是不会被移掉的,如果head.next是和head duplicate的话,移调head.next而不是head.所以这里不需要dummy。

最后需要return head,所以另外用一个指针cur来遍历整个node。

Iterative:
public static ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;  
while(cur!= null){
if (cur.next == null) break;
if (cur.val == cur.next.val){ 
node.next = node.next.next;
}else{
cur = cur.next;
}
}
return head;
}
Recursive:
public static ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode next = deleteDuplicates(head.next);
if (head.val == next.val){
return next;
}
head.next = next;
return head;
}

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5


Recursive:
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
ListNode next = removeElements(head.next, val);
if (head.val == val) return next;
else {
head.next = next;
return head;
}
}

可能head被移掉,所以要引入dummy。另外一个pre前指针来进行连接跳过val的node

Iterative:
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while (head != null){
if (head.val != val){
pre = head;
head = head.next;
}else {
head = head.next;
pre.next = head;//移除
}
}
return dummy.next;
}

Remove Duplicates from Sorted ListII

public static ListNode deleteDuplicates(ListNode head) {
// write your code here
if(head == null || head.next == null)
return head;

ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;

while(head.next != null && head.next.next != null){
if(head.next.val == head.next.next.val){
int val = head.next.val;
while(head.next != null && head.next.val ==val){
head.next = head.next.next;
}
}else{
head = head.next;
}

}
return dummy.next;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: