题解 | #删除链表中重复的结点#
删除链表中重复的结点
http://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef
快慢指针(直接删除法)
以链表:head->1->2->3->3->5->6为例,head为加入的头节点(方便规范化处理)。
慢指针指向head,快指针指向节点1,先让快指针搜索下一个节点与其是否重复
- 若不重复,则快慢指针同时前移一个节点;
- 若重复,则快指针继续移动到该重复段的最后一个节点fast,再将改变慢指针,指向到fast->next,将重复部分跳过(实现删除);
直到快指针到达链尾,结束。
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# @param pHead ListNode类
# @return ListNode类
#
class Solution:
def deleteDuplication(self , pHead: ListNode) -> ListNode:
# 加入头节点(方便对链表进行规范化处理)
head = ListNode(0)
head.next = pHead
low,fast = head,pHead
# 遍历链表
while fast:
# 出现重复节点,继续查找到重复节点的最后一个节点
if fast.next and fast.val == fast.next.val:
while fast.next and fast.val == fast.next.val:
fast = fast.next
low.next = fast.next
fast = fast.next
# 没出现重复节点
else:
fast = fast.next
low = low.next
return head.next