Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
这题的做法是用两个指针pre cur
1.dummy.next= head
2.pre=dummy cur=dummy,next
3.当 指针移到 pre.next 和cur.next 不等的位置 将这个位置加入到 pre.next中去
4.否者就跳过cur
一次遍历 时间是O(n)
代码如下
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a ListNode
def deleteDuplicates(self, head):
if head==None or head.next==None:
return head
dummy=ListNode(0)
dummy.next=head
pre=dummy
cur=dummy.next
while cur!=None:
while cur.next and cur.next.val==pre.next.val:
cur=cur.next
if pre.next==cur:
pre=pre.next
else:
pre.next=cur.next
cur=cur.next
return dummy.next
版权声明：本文为hyperbolechi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。