题目：
给定一个排序链表，删除所有重复的元素每个元素只留下一个。
您在真实的面试中是否遇到过这个题？
样例
给出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