题目描述
输入一个链表，输出该链表中倒数第k个结点。
注意：
该题目不可以用先反转链表再输出第k个结点的方式，因为反转链表会改变该结点的next指向
思路一
使用栈Stack倒序存储，顺序pop第k个结点
实现
/*
public class ListNode {
int val;
ListNode next = null; ListNode(int val) {
this.val = val;
}
}*/
import java.util.Stack;
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
// Stack
Stack<ListNode> stack = new Stack<>();
if(head == null) return null;
int count = 0;
while(head != null){
stack.add(head);
head = head.next;
count++;
}
ListNode res = null;
if(count < k) return res;
for(; k > 0; k--){
res = stack.pop();
}
return res;
}
}
思路二
设链表的长度为 N，寻找第n-k个节点即为第k个结点
设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。
实现
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
// 找到第n-k个节点
if(head == null) return null;
ListNode res = head; // res为第n-k个
while(head != null && k-->0){
head = head.next;
}
if(k >0) return null;
while(head != null){
res = res.next;
head = head.next;
}
return res;
}
}