内容简介:原文链接:前面,我们实现了
原文链接: https://wangwei.one/posts/jav...
前面,我们实现了 两个有序链表的合并 操作,本篇来聊聊,如何删除一个链表的倒数第N个节点。
删除单链表倒数第N个节点
Leetcode 19. Remove Nth Node From End of List
给定一个单链表,如: 1->2->3->4->5
,要求删除倒数第N个节点,假设 N = 2
,并返回头节点。
则返回结果: 1->2->3->5
.
解法一
这一题的难度标记为 medium
,解法一比较容易想出来,我个人觉得难度不大。
思路
循环两遍:
- 先遍历一遍,求得整个链表的长度。
- 再遍历一遍,当总长度
len
减去n
,恰好等于循环的下标i
时,就找到对应要删除的目标元素,将prev
节点与next
节点连接起来即可。
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null){ return null; } int len = 0; for(ListNode curr = head ; curr != null;){ len++; curr = curr.next; } if(len == 0){ return null; } // remove head if(len == n){ return head.next; } ListNode prev = null; int i = 0; for(ListNode curr = head; curr != null;){ i++; prev = curr; curr = curr.next; if(i == (len - n)){ prev.next = curr.next; } } return head; } }
Leetcode测试的运行时间为 6ms
,超过了 98.75%
的 java 代码。
解法二
这种解法,比较巧妙,没有想出来,查了网上的解法,思路如下:
思路
只需要循环一遍,定义两个指针,一个快指针,一个慢指针,让快指针的巧好领先于慢指针 n
步。当快指针到达tail节点时,满指针巧好就是我们需要删除的目标元素。
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null){ return null; } ListNode fast = head; ListNode slow = head; for(int i = 0; i < n; i++){ fast = fast.next; } if(fast == null){ return slow.next; } ListNode prev = null; for(ListNode curr = slow; curr != null; ){ // when fast arrived at tail, remove slow. if(fast == null){ prev.next = curr.next; break; } prev = curr; curr = curr.next; // move fast forward fast = fast.next; } return head; } }
这段代码在LeetCode上的测试结果与解法一的一样。
这种解法与之前的 链表环检测 题目中都使用到了快慢指针,用来定位特定的元素。
以上所述就是小编给大家介绍的《数据结构与算法 | Leetcode 19. Remove Nth Node From End of List》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 算法与数据结构之递归算法
- Python 数据结构与算法 —— 初识算法
- js实现数据结构及算法之排序算法
- 数据结构和算法面试题系列—递归算法总结
- 数据结构和算法面试题系列—随机算法总结
- 数据结构与算法——常用排序算法及其Java实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
iOS游戏编程之从零开始
李华明 / 2013-2 / 59.00元
《iOS游戏编程之从零开始:Cocos2d-x与cocos2d引擎游戏开发》是作者继《android游戏编程之从零开始》热销之后编写的又一本、基于cocos2d—x2.x和cocos2d—iphone版本,讲述ios平台游戏开发的新作。《iOS游戏编程之从零开始:Cocos2d-x与cocos2d引擎游戏开发》分为两个部分共11章,内容主要包括cocos2d—x引擎游戏开发的基础,常用的类、方法及......一起来看看 《iOS游戏编程之从零开始》 这本书的介绍吧!