链表中倒数第 k 个节点
题目描述
输入一个链表,输出该链表中倒数第 k 个节点。为了符合大多数人的习惯,本题从 1 开始计数,即链表的尾节点是倒数第 1 个节点。例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例
示例 1:
1 2
| 给定一个链表:1 -> 2 -> 3 -> 4 -> 5, 和 k = 2 返回链表:4 -> 5
|
题目来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一
先遍历一遍取得链表的长度 length,再遍历一次直到 length - k 的位置,返回此处的节点即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
class Solution { public ListNode getKthFromEnd(ListNode head, int k) { int count = 0; ListNode current = head; while (current != null) { count++; current = current.next; } current = head; for (int i = 0; i < count - k; i++) { current = current.next; } return current; } }
|
解法二
使用双指针的方法,先将一个指针先移动 k 个节点,然后再将两个指针用同样的速度向前移动,当一个指针到达链表末尾时,另一个指针的位置就是倒数第 k 个。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head; ListNode slow = head; for (int i = 0; i < k; i++) { fast = fast.next; } while (fast != null) { if (fast.next != null) { fast = fast.next.next; } else { break; } slow = slow.next; } return slow; } }
|