1，双指针求解
这题要求链表的倒数第k个节点，最简单的方式就是使用两个指针，第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。注意，如果第一个指针还没走k步的时候链表就为空了，我们直接返回null即可。
public ListNode FindKthToTail(ListNode pHead, int k) {
if (pHead == null)
return pHead;
ListNode first = pHead;
ListNode second = pHead;
//第一个指针先走k步
while (k-- > 0) {
if (first == null)
return null;
first = first.next;
}
//然后两个指针在同时前进
while (first != null) {
first = first.next;
second = second.next;
}
return second;
}
2，使用栈解决
这题要求的是返回后面的k个节点，我们只要把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可，原理也比较简单，直接看下代码。
public ListNode FindKthToTail(ListNode pHead, int k) {
Stack<listnode> stack = new Stack<>();
//链表节点压栈
int count = 0;
while (pHead != null) {
stack.push(pHead);
pHead = pHead.next;
count++;
}
if (count < k || k == 0)
return null;
//在出栈串成新的链表
ListNode firstNode = stack.pop();
while (--k > 0) {
ListNode temp = stack.pop();
temp.next = firstNode;
firstNode = temp;
}
return firstNode;
}
3，递归求解 之前讲过链表的逆序打印410，剑指 Offer-从尾到头打印链表，其中有这样一段代码
public void reversePrint(ListNode head) {
if (head == null)
return;
reversePrint(head.next);
System.out.println(head.val);
}
这段代码其实很简单，我们要理解他就要弄懂递归的原理，递归分为两个过程，递和归，看一下下面的图就知道了，先往下传递，当遇到终止条件的时候开始往回走。
前面也刚讲过递归的原理426，什么是递归，通过这篇文章，让你彻底搞懂递归，这题如果使用递归的话，我们先来看一下递归的模板
public ListNode getKthFromEnd(ListNode head, int k) {
//终止条件
if (head == null)
return head;
//递归调用
ListNode node = getKthFromEnd(head.next, k);
//逻辑处理
……
}
终止条件很明显就是当节点head为空的时候，就没法递归了，这里主要看的是逻辑处理部分，当递归往下传递到最底端的时候，就会触底反弹往回走，在往回走的过程中记录下走过的节点，当达到k的时候，说明到达的那个节点就是倒数第k个节点，直接返回即可，如果没有达到k，就返回空，搞懂了上面的过程，代码就很容易写了
//全局变量，记录递归往回走的时候访问的结点数量
int size;
public ListNode FindKthToTail(ListNode pHead, int k) {
//边界条件判断
if (pHead == null)
return pHead;
ListNode node = FindKthToTail(pHead.next, k);
++size;
//从后面数结点数小于k，返回空
if (size < k) {
return null;
} else if (size == k) {
//从后面数访问结点等于k，直接返回传递的结点k即可
return pHead;
} else {
//从后面数访问的结点大于k，说明我们已经找到了，
//直接返回node即可
return node;
}
}
上面代码在仔细一看，当size小于k的时候node节点就是空，所以我们可以把size大于k和小于k合并为一个，这样代码会更简洁一些
int size;
public ListNode FindKthToTail(ListNode pHead, int k) {
if (pHead == null)
return pHead;
ListNode node = FindKthToTail(pHead.next, k);
if (++size == k)
return pHead;
return node;
}
京公网安备 11010502036488号