問題描述
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。(尾結(jié)點(diǎn)是倒數(shù)第一個(gè))
結(jié)點(diǎn)定義如下：
|
1
2
3
4
5
6
7
8
|
public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} |
思路1：
先遍歷鏈表，計(jì)算其長(zhǎng)度length;
然后計(jì)算出倒數(shù)第k個(gè)結(jié)點(diǎn)就是正數(shù)第length - k + 1.
最后再遍歷鏈表，找到所求結(jié)點(diǎn)
時(shí)間復(fù)雜度O(2n),需要遍歷兩次鏈表
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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è)置兩個(gè)指針，一個(gè)初始化指向第一個(gè)結(jié)點(diǎn)，第二個(gè)指向第k個(gè)結(jié)點(diǎn)。然后兩個(gè)指針同步向后移動(dòng)，當(dāng)?shù)诙€(gè)指向尾結(jié)點(diǎn)時(shí)，第一個(gè)指針即指向了倒數(shù)第k個(gè)結(jié)點(diǎn)
代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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個(gè)結(jié)點(diǎn)。
然而這改變了原本的鏈表，且并不會(huì)比思路2更高效
鏈表反轉(zhuǎn)：參考《Java語言實(shí)現(xiàn)反轉(zhuǎn)鏈表代碼示例》
總結(jié)
以上就是本文關(guān)于Java輸出鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)的全部?jī)?nèi)容，如有不足之處，歡迎留言指出，小編一定及時(shí)更正，給大家更好的閱讀體驗(yàn)和幫助，感謝朋友們對(duì)本站的支持！
原文鏈接：http://blog.csdn.net/lilianforever/article/details/51839755
