面试题23-链表中倒数第K个节点

题目要求

现在有一个链表，要求得到倒数第K节点的值。

题目解析

思路一：

• 分析

题目要求得到倒数第k个值，那么我们可以选用一个辅助缓存，辅助计数器
当遍历的位置到达第k个的时候，将头结点存入辅助缓存，从此与遍历一同前进，
当遍历到尾节点的时候，辅助缓存就是倒数第k个。

• 代码段

public static int getReverseOrderOfK(ListNode listNode , int k) throws Exception {
        
        ListNode temp = listNode ;
        int count = 0 ;
        
        if(k<0) {
            throw new Exception("检索值不能为负数") ;
        }
        
        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));
        
    }
    

运行结果

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 链表中倒数第K个节点的值.Demo.getReverseOrderOfK(Demo.java:40)
at 链表中倒数第K个节点的值.Demo.main(Demo.java:69)

---

看完整源码戳源码地址