快捷導(dǎo)航

Java輸出鏈表倒數(shù)第k個節(jié)點(diǎn)

更新時間：2017年10月16日 10:30:54 作者：lilivian

這篇文章主要介紹了Java輸出鏈表倒數(shù)第k個節(jié)點(diǎn)的相關(guān)內(nèi)容，涉及三種設(shè)計(jì)思路及代碼示例，具有一定參考價值，需要的朋友可以了解下。

問題描述

輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點(diǎn)。(尾結(jié)點(diǎn)是倒數(shù)第一個)

結(jié)點(diǎn)定義如下：

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

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

思路1：

先遍歷鏈表，計(jì)算其長度length;
然后計(jì)算出倒數(shù)第k個結(jié)點(diǎn)就是正數(shù)第length - k + 1.
最后再遍歷鏈表，找到所求結(jié)點(diǎn)
時間復(fù)雜度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：

期待只遍歷鏈表一次就能得到。
設(shè)置兩個指針，一個初始化指向第一個結(jié)點(diǎn)，第二個指向第k個結(jié)點(diǎn)。然后兩個指針同步向后移動，當(dāng)?shù)诙€指向尾結(jié)點(diǎn)時，第一個指針即指向了倒數(shù)第k個結(jié)點(diǎn)

代碼：

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：

將鏈表反轉(zhuǎn)，那么原問題就變?yōu)榍笳龜?shù)第k個結(jié)點(diǎn)。
然而這改變了原本的鏈表，且并不會比思路2更高效

鏈表反轉(zhuǎn)：參考《Java語言實(shí)現(xiàn)反轉(zhuǎn)鏈表代碼示例》

總結(jié)

以上就是本文關(guān)于Java輸出鏈表倒數(shù)第k個節(jié)點(diǎn)的全部內(nèi)容，感興趣的朋友可以繼續(xù)參閱：Java編程刪除鏈表中重復(fù)的節(jié)點(diǎn)問題解決思路及源碼分享、Java編程實(shí)現(xiàn)從尾到頭打印鏈表代碼實(shí)例以及本站其他相關(guān)專題，如有不足之處，歡迎留言指出，小編一定及時更正，給大家更好的閱讀體驗(yàn)和幫助，感謝朋友們對本站的支持！

您可能感興趣的文章: