找到链表倒数第k个节点

2017-03-10  本文已影响0人  KevinHwong

问题:输入链表头,以及k的值,返回链表倒数第k个值

解题思路

新建两个指针,指针1和指针2,都指向链表头,指针2 先往前移 k-1位停在第k位,之后指针1指针2开始同步向前移,这样指针1 指针2距离始终保持在k-1。当指针1的next是空的时候,指针2 所指的位置就是倒数第k个节点了。(记得考虑边界情况)


public class ListNode_Test {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
    public static ListNode FindKthToTail(ListNode head,int k){
        ListNode Pointer1 = head;
        ListNode Pointer2 = new ListNode(0);
        //头不能为空,倒数第几个,几要大于0
        if(head == null || k <= 0){ 
            return null;
        }
        for(int i =1;i<k;i++){
            if( Pointer1.next!=null){
                Pointer1 = Pointer1.next;
            }else {
                System.out.println(i);
                return null;
            }
        }
        Pointer2 = head;
        while(Pointer1.next!=null){
            Pointer1 = Pointer1.next;
            Pointer2 = Pointer2.next;
        }
        
        return Pointer2;
    }
    public static void main(String[] args){
        //建立链表(1到10)
        ListNode head = new ListNode(1);
        ListNode p = head;
        System.out.println(p.val);
        for(int i=2;i<11;i++){
            p.next  = new ListNode(i);
            p = p.next;
            System.out.println(p.val);      
        }
        int k =2;
        int ans = FindKthToTail(head,k).val;
        System.out.println("The kth inverse :" + ans ); 
        
    }
    

}


上一篇下一篇

猜你喜欢

热点阅读