第十二題：查找連結清單中倒數第k個節點

題目描述

輸入一個連結清單，輸出該連結清單中倒數第k個節點。

解題思路

方法一：如果連結清單長度為n，那麼計算連結清單中倒數第k個節點，就等價于計算連結清單中正數第n-k+1個節點。基于這個思路實作方法如下：

        首先定義兩個指針都指向頭節點;

        然後讓第一個指針移動k-1步，指向第k個節點;

        最後讓兩個指針同時向後移動，當第一個節點指向末尾時，第二個節點指向的即為第n-k+1個節點，也即連結清單中倒數第k個節點。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode pnode1 = head;
        ListNode pnode2 = head;
        int i = 0;
        for(;pnode1 != null; i++){
            if(i >= k) pnode2 = pnode2.next;
            pnode1 = pnode1.next;
        }
        return k > i ? null:pnode2;
    }
}
           

方法二參考：當出現倒序、反轉等關鍵詞時，可以考慮使用堆棧的方法實作，根據“先進後出”的原則，現将連結清單元素壓棧，實作連結清單反轉，然後取出第k個元素。參考代碼如下：

import java.util.Stack;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode pnode = null;
        int count = 0;
        if(head == null || k <= 0) return null;
        while(head != null){
            stack.push(head);
            head = head.next;
            count++;
        }
        if(count < k) return null;
        for(int i =0;i <k ;i++){
            pnode = stack.pop();
        }
        return pnode;
    }
}