题目描述
输入一个链表,输出该链表中倒数第k个结点。
思路
⚠ 注意边界问题
⚠ 注意特判
- 方法1:
- 倒数第k个 = 第 (size-k) 个
- —使用stack压入节点,再弹出k个
- —直接使用链表数 size
- 倒数第k个 = 第 (size-k) 个
- 方法2:
- –两个指针 p1,p2 都是从左到右移动,p1 先移动,指向 k-1 个数字
- –然后 p2 与 p1 同时右移,直到 p1 移到最后一个 node 处
- –此时 p2 指向的节点就是倒数第 k 个点
### 代码实现
方法一
import java.util.Stack;
ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k <= 0) return null;
Stack<ListNode> nodeStack = new Stack<>();
ListNode node = head;
nodeStack.push(node);
while (node.next != null) {
node = node.next;
nodeStack.push(node);
}
while (k > 1) {
if (nodeStack.empty()) return null;
nodeStack.pop();
k--;
}
if (nodeStack.size() > 0)
return nodeStack.pop();
return null;
}
方法二
ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k <= 0) return null;
ListNode p1 = new ListNode();
ListNode p2 = new ListNode();
p1 = head;
p2 = head;
while (k > 1) {
if (p1.next == null) return null;
p1 = p1.next;
k--;
}
while (p1.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}