首页 > 其他 > 详细

输入一个单向链表,输出该链表中倒数第k个结点

时间:2020-07-04 20:11:08      阅读:54      评论:0      收藏:0      [点我收藏+]

思路:利用快慢指针能实现在时间复杂度为O(n)的情况下,找到第k个节点

1,快指针先走k步

2,快慢指针一起走,直到快指针指向null时,慢指针所在位置就是倒数第k个节点

public static void main(String[] args) {
       ListNode eight = new ListNode(8,null);
       ListNode sevent = new ListNode(7,eight);
       ListNode six = new ListNode(6,sevent);
       ListNode firth = new ListNode(5,six);
       ListNode fourth = new ListNode(4,firth);
       ListNode three = new ListNode(3,fourth);
       ListNode two = new ListNode(2,three);
       ListNode one = new ListNode(1,two);

       int k = 3;
        ListNode low = one;
        ListNode fast = one;
       while (k > 0){
           fast = fast.next;
           k--;
       }
       while (fast != null){
           fast = fast.next;
           low = low.next;
       }
        System.out.println(fast);
        System.out.println(low.val);
    }

 

输入一个单向链表,输出该链表中倒数第k个结点

原文:https://www.cnblogs.com/dongma/p/13236185.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!