題目要求
現(xiàn)在有一個(gè)鏈表柬批，要求得到倒數(shù)第K節(jié)點(diǎn)的值荆隘。
題目解析
思路一：
- 分析
題目要求得到倒數(shù)第k個(gè)值精偿，那么我們可以選用一個(gè)輔助緩存蜒谤，輔助計(jì)數(shù)器
當(dāng)遍歷的位置到達(dá)第k個(gè)的時(shí)候棘劣，將頭結(jié)點(diǎn)存入輔助緩存俏让，從此與遍歷一同前進(jìn)，
當(dāng)遍歷到尾節(jié)點(diǎn)的時(shí)候，輔助緩存就是倒數(shù)第k個(gè)首昔。
- 代碼段
public static int getReverseOrderOfK(ListNode listNode , int k) throws Exception {
ListNode temp = listNode ;
int count = 0 ;
if(k<0) {
throw new Exception("檢索值不能為負(fù)數(shù)") ;
}
if(listNode == null ) {
throw new Exception("鏈表為空") ;
}
while(listNode != null && listNode.getNext() != null ) {
listNode = listNode.getNext() ;
count ++ ;
if( count > k -1 ) {
temp = temp.getNext() ;
}
System.out.println(temp.getValue() + "與" + listNode.getValue());
}
if(count < k-1 ) {
throw new Exception("鏈表長度小于" + k) ;
}
return temp.getValue() ;
}
測試代碼
public static void main(String[] args) throws Exception {
ListNode node1 = new ListNode() ;
ListNode node2 = new ListNode() ;
ListNode node3 = new ListNode() ;
ListNode node4 = new ListNode() ;
ListNode node5 = new ListNode() ;
node1.setValue(1);
node2.setValue(2);
node3.setValue(3);
node4.setValue(4);
node5.setValue(5);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
System.out.println(getReverseOrderOfK(node1 , 3));
System.out.println(getReverseOrderOfK(node1 , 5));
System.out.println(getReverseOrderOfK(node1 , 0));
System.out.println(getReverseOrderOfK(node1 , 6));
}
運(yùn)行結(jié)果
1與2
1與3
2與4
3與5
3
1與2
1與3
1與4
1與5
1
2與2
3與3
4與4
5與5
5
1與2
1與3
1與4
1與5
Exception in thread "main" java.lang.Exception: 鏈表長度小于6
at 鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)的值.Demo.getReverseOrderOfK(Demo.java:40)
at 鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)的值.Demo.main(Demo.java:69)
