Java實作輸出鍊錶倒數第k個節點的範例程式碼分享

這篇文章主要介紹了Java輸出鍊錶倒數第k個節點的相關內容，涉及三種設計想法及程式碼範例，具有一定參考價值，需要的朋友可以了解下。

問題描述

輸入一個鍊錶，輸出該鍊錶中倒數第k個結點。 (尾結點是倒數第一個)

結點定義如下：

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

  ListNode(int val) {
    this.val = val;
  }
}

#想法1：

先遍歷鍊錶，計算其長度length;
然後計算出倒數第k個結點就是正數第length - k + 1.
最後再遍歷鍊錶，找到所求結點
時間複雜度O(2n),需要遍歷兩次鍊錶

#程式碼如下：

##

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    int length = 1;
    while(p.next != null){
      length++;
      p = p.next;
    }
    int index = length - k + 1;
    if(index <= 0){
      return null;
    }
    p = head;
    int num = 1;
    while(p.next != null && num < index){
      num++;
      p = p.next;
    }
    if(num < index){
      return null;
    }else{
      return p;
    }
  }

思路2：

期待只遍歷鍊錶一次就能得到。

設定兩個指針，一個初始化指向第一個結點，第二個指向第k個結點。然後兩個指標同步向後移動，當第二個指向尾結點時，第一個指標即指向了倒數第k個結點

程式碼：

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    ListNode q = head;
    for(int i = 0; i < k-1; i++){
      if(q == null){
        return null;
      }
      q = q.next;
    }
    if(q == null){
      return null;
    }
    while(q.next != null){
      p = p.next;
      q = q.next;
    }
    return p;
  }

思路3：

#將鍊錶反轉，那麼原問題就變成求正數第k個結點。

然而這改變了原本的鍊錶，且不會比思路2更有效率

鍊錶反轉：參考《Java語言實作反轉鍊錶程式碼範例》

總結

以上是Java實作輸出鍊錶倒數第k個節點的範例程式碼分享的詳細內容。更多資訊請關注PHP中文網其他相關文章！