lintcode :Remove Duplicates from Sorted List 删除排序链表中的重复元素

题目:

删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素每个元素只留下一个。

 

您在真实的面试中是否遇到过这个题?

样例

给出1->1->2->null,返回 1->2->null

给出1->1->2->3->3->null,返回 1->2->3->null

解题:

Java程序

/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param ListNode head is the head of the linked list
* @return: ListNode head of linked list
*/
public static ListNode deleteDuplicates(ListNode head) {
// write your code here
ListNode p = new ListNode(0);
p.next = head;
if(head==null)
return null;
while(head.next!=null){
if(head.val==head.next.val){
head.next = head.next.next;
}else
head = head.next;
} return p.next;
}
}

总耗时: 2604 ms

这个是两个比较,相同就删除一个直接删除,指针变换的比较多

可以向上面一个删除有序数组中相同的元素那样进行

head指向开始节点,current向前走,知道current.val!=head.val时候,head的指针指向current节点

Java程序:

/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param ListNode head is the head of the linked list
* @return: ListNode head of linked list
*/
public static ListNode deleteDuplicates(ListNode head) {
// write your code here
ListNode p = new ListNode(0);
p.next = head;
ListNode current = new ListNode(0);
current.next = head;
current = current.next;
if(head==null)
return null;
while(head!=null){
while(current!=null && head.val==current.val){
current = current.next;
}
head.next = current;
head = head.next;
}
return p.next;
}
}

总耗时: 1808 ms

Python程序:

"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: A ListNode
@return: A ListNode
"""
def deleteDuplicates(self, head):
# write your code here
p = ListNode(0)
p.next = head
if head==None:
return None
while head.next!=None:
if head.val==head.next.val:
head.next = head.next.next;
else:
head=head.next
return p.next

总耗时: 319 ms

上面的第二个方法

Python程序:

"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: A ListNode
@return: A ListNode
"""
def deleteDuplicates(self, head):
# write your code here
if head==None:
return None
p = ListNode(0)
p.next = head
cur = ListNode(0)
cur.next = head
cur = cur.next
while head!=None:
while cur!=None and cur.val==head.val:
cur = cur.next
head.next = cur
head = head.next
return p.next

总耗时: 471 ms

上一篇:使用GDI+进行图片处理时要注意的问题


下一篇:LeetCode#26 | Remove Duplicates from Sorted Array 删除有序数组中的重复元素