美文网首页
找到链表倒数第k个节点

找到链表倒数第k个节点

作者: KevinHwong | 来源:发表于2017-03-10 12:37 被阅读0次

    问题:输入链表头,以及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 ); 
            
        }
        
    
    }
    
    
    

    相关文章

      网友评论

          本文标题:找到链表倒数第k个节点

          本文链接:https://www.haomeiwen.com/subject/ynvngttx.html