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

删除链表中重复的结点

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 12:17
已编辑
商丘师范学院 Java
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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