在線題目鏈接：鏈表中倒數第k的節點

文章目錄

• 1 題目描述
• 2 題目分析
• • 2.1 Java代碼
  • 2.2 C++代碼
• 3 總結

1 題目描述

輸入一個鏈表，輸出該鏈表中倒數第k個結點。

2 題目分析

這道題比較簡單。常規做法是先求出鏈表的總的節點個數n，然后再從頭開始找第n-k+1個節點，這個節點就是倒數第k個節點。這種方法很好實現。

還有一種比較巧妙的解法：指定兩個指針p和q指向鏈表頭，讓p先走k-1步，然后當p走了k-1步之后，q也開始從頭開始往后走。那么此時p與q之間的距離為k-1。當p走到鏈表的末尾后，因為q與p距離k-1，所以q剛好在倒數第k個位置。
如下圖

假設上面是需要找到倒數第3個節點。先讓p1走3-1=2步，然后p2與p1同步開始跑，當p1到最后一個節點時，p2剛好位于倒數第3個節點。

2.1 Java代碼

public class Solution {public ListNode FindKthToTail(ListNode head,int k) {ListNode p, q;p = q = head;int i = 0;for (; p != null; i++) {if (i >= k)q = q.next;p = p.next;}return i < k ? null : q;} }

2.2 C++代碼

class Solution { public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {ListNode* p=pListHead,*q=pListHead;int i=0;for(;p!=nullptr;i++){if(i>=k)q=q->next;p=p->next;}return i<k?nullptr:q; } };

3 總結

常規做法比較簡單好想，使用兩個指針前后移動這種方法更加高效

探討學習加：
個人qq：1126137994
個人微信：liu1126137994

總結

以上是生活随笔為你收集整理的【剑指offer - C++/Java】14、链表中倒数第k的节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。