10删除链表中指定结点★★★★

10删除链表中指定结点★★★★

• • 题目描述（难度：中等）
  • 单链表结构
  • 方法一
  • • 复杂度分析
  • 主函数
  • 参考文献

题目描述（难度：中等）

假设给定链表 1->2->3->4->5->6->7 中指向第 5 个元素的指针，要求把结点 5 删掉，删除后链表变为 1->2->3->4->6->7。（来源：小米）

单链表结构

class LNode:def __init__(self):self.data = None # 数据域self.next = None # 指针域

• 由于单链表中每个结点的地址都存储在其前驱结点的指针域中，因此，对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。
• 注意：在修改结点指针域的时候，记录下后继结点的地址，否则会丢失后继结点。

方法一

def printList(head):cur = head.nextwhile cur != None:print(cur.data, '', end='')cur = cur.next# 给定单链表中某个结点，删除该结点
def RemoveNode(p):# 如果结点为空，或结点p无后继结点则无法删除if p == None or p.next == None:return Falsep.data = p.next.datatmp = p.nextp.next = tmp.nextreturn True

复杂度分析

• 时间复杂度为$O(1)$，不需要遍历链表，只需要完成一个数据复制与结点删除的操作。
• 空间复杂度为$O(1)$，只需常量个指针变量来保存结点的地址信息。

主函数

if __name__ == "__main__":head = LNode()  # 链表头结点head.next = Nonecur = headp = Nonek = int(input("请输入指定结点:"))# 构造链表link = [1, 2, 3, 4, 5, 6, 7]for i in link:tmp = LNode()tmp.data = itmp.next = Nonecur.next = tmpcur = tmpif i == k:p = tmpprint("删除结点", p.data, "前链表: ", end='\n')printList(head)result = RemoveNode(p)if result:print("\n删除该结点后链表:", end='\n')printList(head)

参考文献

[1] 何海涛. 剑指Offer：名企面试官精讲典型编程题（第2版）. 北京： 电子工业出版社，2017
[2] 张波，楚秦. Python程序员面试算法宝典. 北京：机械工业出版社，2018

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！