题解 | #删除链表中重复的结点#

删除链表中重复的结点

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
全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 11:45
你不要过来啊啊啊啊啊啊啊
码农索隆:对面:“今天你不面也得面”
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务