中国制造网入驻,搜索引擎优化策略不包括,建设网站怎么添加端口映射,网站上的文章做参考文献19. 删除链表的倒数第 N 个结点 给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。 此题目为链表题#xff0c;拿出我们的杀手锏#xff0c;链表解题经典三把斧#xff1a;
哑巴节点栈快慢指针
关于内存问题#xff1a;由于Swift及…19. 删除链表的倒数第 N 个结点 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 此题目为链表题拿出我们的杀手锏链表解题经典三把斧
哑巴节点栈快慢指针
关于内存问题由于Swift及OC均有ARC内存机制因此删除的节点内容未主动释放如在手动内存管理的情况下需要释放被删除节点的内存占用。
方法一、计算链表长度
先求出链表长度L再将链表从头移动到L-n1的位置删除其下一个节点。
时间复杂度O(n)一次求长度n极端情况下的一次遍历2n-O(n) 空间复杂度O(1)
Swift
//计算链表长度, 删除l-n1的位置
func removeNthFromEnd(_ head: ListNode?, _ n: Int) - ListNode? {let dummyNode ListNode(0, head);let len getLenOfListNode(head)var current:ListNode? dummyNodefor _ in 1..len-n1 {current current?.next}current?.next current?.next?.next//MRC Or ARC被释放的节点内存需要处理吗let ans dummyNode.nextreturn ans}func getLenOfListNode(_ listNode:ListNode?) - Int {var len 0var current listNodewhile let cur current {current cur.nextlen 1}return len}OC
//计算链表长度, 删除l-n1的位置
- (ListNodeOC *)removeNthFromEnd:(ListNodeOC *)head atReverseIdx:(NSInteger)n {//构造虚拟头节点ListNodeOC *dummyNode [[ListNodeOC alloc] initWithVal:0 next:head];NSInteger len [self lenOfListNode:head];ListNodeOC *cur dummyNode;for (NSInteger i1; ilen-n1; i) {cur cur.next;}cur.next cur.next.next;return dummyNode.next;
}解法二、栈
先将链表入栈再出栈n个元素后栈顶部的元素就是我们需要删除的节点的前一个节点。
时间复杂度O(n) 空间复杂度O(n)
Swift //入栈后弹栈n次即可func removeNthFromEnd(_ head: ListNode?, _ n: Int) - ListNode? {//构造影子节点let fickNode ListNode(0)fickNode.next headlet stack StackListNode()var cur:ListNode? fickNodewhile let currentNode cur {stack.push(currentNode)cur currentNode.next}for _ in 0..n {let _ stack.pop()}if let preNode stack.top() {preNode.next preNode.next?.next}return fickNode.next}OC
- (ListNodeOC *)removeNthFromEnd:(ListNodeOC *)head atReverseIdx:(NSInteger)n {ListNodeOC *dummyNode [[ListNodeOC alloc] initWithVal:0 next:head];StackOC *stack [[StackOC alloc] init];//先入栈ListNodeOC *cur dummyNode;while (cur) {[stack push:cur];cur cur.next;}//出栈n个元素for (NSInteger i0; in; i) {[stack pop];}//删除最后一个元素cur [stack top];cur.next cur.next.next;[stack cleanAll];return dummyNode.next;
}双指针
创建哑巴节点有两个指针均指向哑巴节点首先移动第2个指针n次此时第1、2个指针相距n个节点然后同时移动1、2两个节点直至第2个指针指向最后一个元素此时的第1个指针指向的节点就是倒数第n个元素的前一个元素。
时间复杂度O(n) 空间复杂度O(1)
Swift func removeNthFromEnd(_ head: ListNode?, _ n: Int) - ListNode? {//构造影子节点为指针操作预留空间let dummyNode ListNode(0, head)var first:ListNode? dummyNodevar second:ListNode? dummyNodevar current:ListNode? dummyNodefor _ in 0..n {if let cur current {second cur.nextcurrent second}}//同时移动两个指针,直至2到达结尾while let _ current?.next {first first?.nextsecond second?.nextcurrent second}first?.next first?.next?.nextreturn dummyNode.next}OC
- (ListNodeOC *)removeNthFromEnd:(ListNodeOC *)head atReverseIdx:(NSInteger)n {ListNodeOC *dummyNode [[ListNodeOC alloc] initWithVal:0 next:head];ListNodeOC *firstNode dummyNode;ListNodeOC *secondNode dummyNode;//先移动指针让两个指针差值为nfor (NSInteger i0; in; i) {secondNode secondNode.next;}//同时移动两个指针当第二个指针指向最后一个元素的时候第一个指针指向的正是倒数第n个元素while (secondNode.next) {firstNode firstNode.next;secondNode secondNode.next;}firstNode.next firstNode.next.next;return dummyNode.next;
}
