文章目錄
- 題目
- 思路一
- 思路二
題目
輸入一個鏈表，輸出該鏈表中倒數第k個結點，
思路一
求倒數第k個，可以轉換成求正數個數
/**
* 求倒數第k個，可以轉換成求正數第多少個呢？
* @param head
* @param k
* @return
*/
public CListNode FindKthToTail(CListNode head, int k) {
if (head == null || k < 0) return null;
//求節點總數
int sum = 0;
CListNode temp = head;
while (temp != null) {
sum++;
temp = temp.next;
}
if (sum < k) return null;//總數小于倒數第k個
//倒數第k個是正數第sum - k
sum = sum - k;
while (sum>0){
head = head.next;//向后移動
sum--;
}
return head;
}
思路二
使用快慢指標
使用如圖的快慢指標，首先讓快指標先行k步，然后讓快慢指標每次同行一步，直到快指標指向空節點，慢指標就是倒數第K個節點，
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null||k<0) return null;//考慮頭指標為空的情況
ListNode slow = head;//慢指標
ListNode fast = head;//快指標
//先將快指標移動到慢指標的后k個
int index = k;
while (index > 0) {
index--;
if(fast!=null)fast = fast.next;//如果總長小于k則回傳空
else return null;
}
//現在將快慢指標同時向后移動，直到快指標移動到最后一個元素，此時慢指標所指的即為倒數第k個元素
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/252179.html
標籤：其他