常德企业网站建设,广州站在哪里,国内代理,国外家居创意空间设计文章目录 1. 题目2. 思路及代码实现#xff08;Python#xff09;2.1 计算链表长度2.2 栈 1. 题目
给你一个链表#xff0c;删除链表的倒数第 n n n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a;
输入#xff1a; h e a d [ 1 , 2 , 3 , 4 , 5 ] , n… 文章目录 1. 题目2. 思路及代码实现Python2.1 计算链表长度2.2 栈 1. 题目
给你一个链表删除链表的倒数第 n n n 个结点并且返回链表的头结点。
示例 1
输入 h e a d [ 1 , 2 , 3 , 4 , 5 ] , n 2 head [1,2,3,4,5], n 2 head[1,2,3,4,5],n2 输出 [ 1 , 2 , 3 , 5 ] [1,2,3,5] [1,2,3,5]
示例 2
输入 h e a d [ 1 ] , n 1 head [1], n 1 head[1],n1 输出 [ ] [ ] []
示例 3
输入 h e a d [ 1 , 2 ] , n 1 head [1,2], n 1 head[1,2],n1 输出 [ 1 ] [1] [1] 提示 1 s z 30 1 sz 30 1sz30其中 s z sz sz 为链表中的节点数目 0 N o d e . v a l 100 0 Node.val 100 0Node.val100 1 n s z 1 n sz 1nsz
2. 思路及代码实现Python
在对链表进行操作时一种常用的技巧是添加一个哑节点dummy node它的 next \textit{next} next 指针指向链表的头节点。这样一来就不需要对头节点进行特殊的判断了。
例如在本题中如果我们要删除节点 y y y我们需要知道节点 y y y 的前驱节点 x x x并将 x x x 的指针指向 y y y 的后继节点。但由于头节点不存在前驱节点因此我们需要在删除头节点时进行特殊判断。但如果我们添加了哑节点那么头节点的前驱节点就是哑节点本身此时我们就只需要考虑通用的情况即可。
题解引用来源力扣官方题解
2.1 计算链表长度
一种容易想到的方法是我们首先从头节点开始对链表进行一次遍历得到链表的长度 L L L。随后我们再从头节点开始对链表进行一次遍历当遍历到第 L − n 1 L−n1 L−n1 个节点时它就是我们需要删除的节点。
为了方便删除操作我们可以从哑节点开始遍历 L − n 1 L−n1 L−n1 个节点。当遍历到第 L − n 1 L−n1 L−n1 个节点时它的下一个节点就是我们需要删除的节点这样我们只需要修改一次指针就能完成删除操作。 该算法的时间复杂度为 O ( L ) O(L) O(L)其中 L L L 是链表的长度空间复杂度为 O ( 1 ) O(1) O(1)。
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) - ListNode:def getLength(head: ListNode) - int:length 0while head:length 1head head.nextreturn lengthdummy ListNode(0, head)length getLength(head)cur dummyfor i in range(1, length - n 1):cur cur.nextcur.next cur.next.nextreturn dummy.next执行用时44 ms 消耗内存16.45 MB
2.2 栈
我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则我们弹出栈的第 n n n 个节点就是需要删除的节点并且目前栈顶的节点就是待删除节点的前驱节点。这样一来删除操作就变得十分方便了。
上一个方法用链表结构存储每个节点的指向节点因此节省存储空间无需存储所有的节点。而用栈的方法在Python中用元素带顺序的列表来表征进出操作实现逻辑很直观简单但需牺牲部分存储空间。
该算法的时间复杂度为 O ( L ) O(L) O(L)空间复杂度也为 O ( L ) O(L) O(L)。
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) - ListNode:dummy ListNode(0, head)stack list()cur dummywhile cur:stack.append(cur)cur cur.nextfor i in range(n):stack.pop()prev stack[-1]prev.next prev.next.nextreturn dummy.next执行用时27 ms 消耗内存16.38 MB
