一、题目描述
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
二、我的题解
1. 方法一：两次遍历
输出倒数第 K 个节点。
但是链表只能正向遍历，而且我们不知道倒数第 K 个节点是正数第几个节点。
所以我的思路是先通过遍历知道链表总共有多少个节点，再通过计算（相减）知道倒数第 K 个节点是正数第几个节点。
然后再去正向遍历到它。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getKthFromEnd(head *ListNode, k int) *ListNode {
if head == nil {
return nil
}
curr := head
n := 0
for curr != nil { //计算链表长度
n++
curr = curr.Next
}
if (k >= 0) && (k <= n) {
i := n - k
for i > 0 { //循环 n - k 次，向后移 n - k 次
head = head.Next
i--
}
return head
} else {
return nil
}
return head
}
评判结果：
复杂度分析：
-
时间复杂度：O(n)，其中 n 为链表的长度。需要 两次遍历。
-
空间复杂度：O(1) 。
遍历两次终究麻烦，以下这个方法巧妙地使用双指针，只需要遍历一次：
2. 方法二：双指针
快慢指针的思想：
我们将第一个指针 fast 指向链表的第 k + 1 个节点，第二个指针 slow 指向链表的第一个节点，此时二个指针之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针 fast 走到链表的 尾部空节点 时，则第二个指针 slow 刚好指向链表的倒数第 k 个节点。
我们首先将 fast 指向链表的头节点，然后向后走 k 步，则此时 fast 指针刚好指向链表的第 k + 1个节点。
我们首先将 slow 指向链表的头节点，同时 fast 同步向后走，当 fast 指针指向链表的尾部空节点时，则此时返回 slow 所指向的节点即可。
以上就是双指针的思想。
我在实现的时候，和上面的描述有点细微差别。我使得快慢指针之间相差 k-1 个节点，那么当快指针指到最后一个节点（不是空节点哦）时，慢指针刚好到倒数第 k 个节点。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getKthFromEnd(head *ListNode, k int) *ListNode {
if head == nil {
return nil
}
end := head //先走的节点
pre := head //后走的节点
n := 0
if k >= 0 {
for end.Next != nil { //end 指到最后一个节点停止
n++
if n < k { //end 独自走了k-1次，和 pre 相差 k-1 个节点。然后它两一起走(else部分)
end = end.Next
} else { //pre 从 n = k 时开始走
end = end.Next
pre = pre.Next
}
}
if k <= n+1 { //n+1是节点数
return pre
} else {
return nil
}
} else {
return nil
}
}
评判结果：
复杂度分析
-
时间复杂度：O(n)，其中 n 为链表的长度。我们使用快慢指针，只需要 一次遍历 即可，复杂度为 O(n) 。
-
空间复杂度：O(1) 。
三、一点讨论
其实刚开始我打算先反转链表，然后遍历到第K个节点。
但是我发现示例中返回的链表是正向的。
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
所以反转链表是不可行的。我们要保证链表的正向性。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/118986.html
