剑指 Offer 22. 链表中倒数第k个节点
题目
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
例如,一个链表有 6
个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6
。这个链表的倒数第 3
个节点是值为 4
的节点。
示例:
给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
解题方法一
/**
* 自己想的 实质是双指针
* 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
* 内存消耗:36.3 MB, 在所有 Java 提交中击败了27.58%的用户
*
* @param head
* @param k
* @return
*/
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null) return null;
int len = 0;
ListNode pre = head;
while (pre != null){
len++;
pre = pre.next;
}
if (k > len) return null;
if (k == len) return head;
ListNode res = head;
ListNode priority = head;
while (k - 1 != 0){
priority = priority.next;
k--;
}
while (priority != null){
priority = priority.next;
if (priority == null){
break;
}
res = res.next;
}
return res;
}
解题方法二
/**
* 顺序查找
* 首先求出链表的长度 n,然后顺序遍历到链表的第 n−k 个节点返回即可。
*
* 时间复杂度:O(n),其中 n 为链表的长度。需要两次遍历。
* 空间复杂度:O(1)。
*
* @param head
* @param k
* @return
*/
public ListNode getKthFromEnd2(ListNode head, int k) {
int n = 0;
ListNode node = null;
// 求出链表的长度 n
for (node = head; node != null; node = node.next) {
n++;
}
// 序遍历到链表的第 n−k 个节点返回
for (node = head; n > k; n--) {
node = node.next;
}
return node;
}
解题方法三
/**
* 双指针
*
* 首先将fast 指向链表的头节点,然后向后走 k 步,则此时fast 指针刚好指向链表的第 k+1 个节点。
* 将 slow 指向链表的头节点,同时 \slow 与 fast 同步向后走,当 fast 指针指向链表的尾部空节点时,
* 则此时返回 slow 所指向的节点即可
*
*时间复杂度:O(n),其中 n 为链表的长度。我们使用快慢指针,只需要一次遍历即可,复杂度为 O(n)。
* 空间复杂度:O(1)。
*
* @param head
* @param k
* @return
*/
public ListNode getKthFromEnd3(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && k > 0) {
fast = fast.next;
k--;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
微信关注
本站为非盈利性站点,所有资源、文章等仅供学习参考,并不贩卖软件且不存在任何商业目的及用途,如果您访问和下载某文件,表示您同意只将此文件用于参考、学习而非其他用途。
本站所发布的一切软件资源、文章内容、页面内容可能整理来自于互联网,在此郑重声明本站仅限用于学习和研究目的;并告知用户不得将上述内容用于商业或者非法用途,否则一切后果请用户自负。
如果本站相关内容有侵犯到您的合法权益,请仔细阅读本站公布的投诉指引页相关内容联系我,依法依规进行处理!
作者:理想
链接:https://www.imyjs.cn/archives/583
本站所发布的一切软件资源、文章内容、页面内容可能整理来自于互联网,在此郑重声明本站仅限用于学习和研究目的;并告知用户不得将上述内容用于商业或者非法用途,否则一切后果请用户自负。
如果本站相关内容有侵犯到您的合法权益,请仔细阅读本站公布的投诉指引页相关内容联系我,依法依规进行处理!
作者:理想
链接:https://www.imyjs.cn/archives/583
THE END
0
二维码


剑指 Offer 22. 链表中倒数第k个节点
题目
输入一个链表,输出该链表中倒数第k个节点。……

文章目录
关闭

共有 0 条评论