李峰峰博客
总有一天你会为今天的自己感到自豪一、概述
求链表倒数第k个结点是剑指 offer 上一道经典的算法题，并且还有很多类似的算法题，比如求链表的中间结点等，他们的解题思路都是一样的。解类似的题目，最笨的一个方法是先遍历一下整个链表，确定链表结点的数量后再根据数量找出倒数第k个结点或中间的那个结点。不过，本文并不去考虑这种笨办法，还有更好的实现方法。
题目描述：
输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。
二、实现思路及代码
对于解决此类问题，最好的方法是使用两个指针实现，首先将第一个指针pNode前进 k 步，然后qNode才开始前进，后面pNode、qNode同时往前移动，当pNode指向尾结点时，pNode指向的结点就是倒数第k个结点。如下图：
当然，链表和上篇文章一样（以后如果不特别说明则链表不变）：
class LinkList {
var value: Int
var next: LinkList?
init(_ val: Int) {
value = val
}
}//求链表倒数第k个结点
func theKthLinkList(_ linkList:LinkList,_ k:Int)->LinkList?{
var pNode = linkList
var tempK = k
//pNode先前进k步
while tempK > 0 && pNode.next != nil{
tempK -= 1
pNode = pNode.next!
}
//如果到这里仍然tempK > 0说明k大于结点总数
if(tempK > 0){
print("k的值过大不合法！")
return nil
}
//之后qNode从头结点开始跟着pNode一起前进，直到pNode为尾结点
var qNode = linkList
while pNode.next != nil{
pNode = pNode.next!
qNode = qNode.next!
}
return qNode
}上面就是就链表倒数第k个结点的方法。
对于求链表中间的那个结点（题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点），实现方法还是类似的。也是使用pNode和qNode两个指针实现，方法是。用两个指针pNode和qNode从链表头节点开始，pNode每次向后移动两步，qNode每次移动一步，直到pNode移到到尾节点，那么qNode就是中间结点。
还有一题类似的是判断单链表是否存在环（题目描述：输入一个单向链表，判断链表是否有环？），解题思想还是一样的，通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。
感兴趣的可以自己敲着试下。
原创文章，转载请注明： 转载自李峰峰博客
本文链接地址: Swift算法实现之链表倒数第k个结点
