题目描述
思路
这题的大体思路如下:
1. 首先让一个引用 p 指向 正向第 k 个节点,另一个引用 q 指向 头节点
2. p q, 同时向后移动,直到 p 到达了链表的末尾为空,那么此时 q 就是倒数第 k 个节点。
以上的情况可能由于描述问题,建议自己画一遍就明白了。
具体的原理:
可以看下图,
一开始 p 距离起点的距离是 k
我们整体把pq向右移动,
知道p到达终点,
那么可以得出 q距离起点的距离也是 k。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fakeHead=new ListNode(),p=fakeHead;
fakeHead.next=head;
for(int i=0;i<k;i++){
p=p.next;
}
ListNode q=fakeHead;
while(p!=null){
p=p.next;
q=q.next;
}
return q;
}
}