題目描述
輸入一個鏈表冰评，輸出該鏈表中倒數(shù)第k個結點。
解題思路
經典的雙指針法驻民。定義兩個指針，第一個指針從鏈表的頭指針開始遍歷向前走k-1步履怯，第二個指針保持不動回还，從第k步開始，第二個指針也開始從鏈表的頭指針開始遍歷虑乖，由于兩個指針的距離保持在k-1懦趋，當?shù)谝粋€指針到達鏈表的尾節(jié)點時，第二個指針剛好指向倒數(shù)第k個節(jié)點疹味。
關注要點
1）鏈表頭指針是否為空仅叫，若為空則直接返回回null
2）k是否為0，k為0也就是要查找倒數(shù)第0個節(jié)點糙捺，由于計數(shù)一般是從1開始的诫咱，所有輸入0沒有實際意義，返回null
3）k是否超出鏈表的長度坎缭，如果鏈表的節(jié)點個數(shù)少于k，則在指針后移的過程中會出現(xiàn)next指向空指針的錯誤掏呼，所以程序中要加一個判斷
參考代碼（Java）
- 結構定義
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
- 解法一代碼
public class Demo03 {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null || k==0) {
return null;
}
ListNode p1 = head;
//判斷k是否超過鏈表節(jié)點的個數(shù)憎夷，注意是 i 從1~k-1
for (int i = 1; i < k; i++) {
if(p1.next!=null) {
p1=p1.next;
}else {
return null;
}
}
ListNode p2 = head;
while(p1.next!=null) {
p1=p1.next;
p2=p2.next;
}
return p2;
}
}
- 測試主方法
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
ListNode listNode4 = new ListNode(4);
listNode3.next = listNode4;
listNode2.next = listNode3;
listNode.next = listNode2;
ListNode tail = FindKthToTail(listNode,2);
System.out.println(tail.val);
}
- 輸出結果
3
- 解法二代碼（用棧）
public class Demo03 {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k == 0) {
return null;
}
// 可以先把鏈表反轉拾给，然后找出第k個
Stack<ListNode> stack = new Stack<ListNode>();
int count = 0;
while (head != null) {
stack.push(head);
head = head.next;
count++;
}
if (count < k) {
return null;
}
ListNode knode = null;
for (int i = 0; i < k; i++) {
knode = stack.pop();
}
return knode;
}
}
