12、链表中倒数第k个结点

题目

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

思路

为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针:

(1)第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;

(2)从第k步开始,第二个指针也开始从链表的头指针开始遍历;

(3)由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点。

下图展示了在有6个结点的链表上找倒数第3个结点的过程
  

代码

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        //遍历整个链表长度length,如果给出的k值大于length,那么直接出错
        int length =0;
        ListNode head1 = head;
        while(head1!=null){
            length++;
            head1 = head1.next;
        }
        if(k<=0 || k>length)
            return null;
        //找到链表的第一个和第二个指针,分别为ahead和behind
        ListNode ahead = head;
        ListNode behind =head;;
        //将ahead的位置移到k-1 位置,此时链表起始位为behind
        for(int i=0;i<k-1;i++){
            if(ahead.next!=null){
                ahead = ahead.next;
            }
        }
        //使用ahead遍历剩下的链表长度,如果ahead到达末尾,那么behind到达的位置就是倒数第K个节点
        while(ahead.next!=null){
            ahead = ahead.next;
            behind = behind.next;
        }
        return behind;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:35
虽然不怎么光彩,经过这件事,可能我真的要去认同“面试八股文早该淘汰!不会用AI作弊的程序员=新时代文盲!”这句话了
HellowordX:Ai的出现是解放劳动力的,不是用来破坏公平竞争环境的,这样下去,轻则取消所有线上面试,严重了会影响整个行业对所有人产生影响,企业会拉高入职考核各种离谱考核会层出不穷
你找工作的时候用AI吗?
点赞 评论 收藏
分享
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务