每天一道劍指offer-鏈表中倒數第k個結點

• 2019 年 10 月 4 日
• 筆記

今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。

昨天的題解

題目

每天一道劍指offer-鏈表中倒數第k個結點 來源：牛客網對應專題

題目詳述

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

題目詳解

思路

• 就是快慢指針，快指針先走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) {          int length = 0;          ListNode tempHead = head;          while(tempHead != null)          {              length++;//這裡計算鏈表的長度              tempHead = tempHead.next;          }          if(k > length || k <=0)//因為倒數第K個節點，如果超過鏈表長度可不行呀              return null;          ListNode before = head;          ListNode after = head;          for(int i=0;i<k-1;i++)快指針先走k-1步              before = before.next;          while(before.next != null)          {              before = before.next;              after = after.next;//快慢指針一起走。          }          return after;      }  }

程式碼截圖(為了避免程式碼排版錯亂）