Java&Go-剑指Offer面试题22:链表中倒数第k个结点-双指针

链表中倒数第k个结点

http://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a

题目:输入一个链表,输出该链表中倒数第k个结点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾结点是倒数第1个结点。例如一个链表有6个结点,从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

  • 算法
    • 1.在头节点前面建立伪节点
    • 2.双指针,前指针先走到第k个节点,随后前后指针一起走,当前指针走到结尾null节点时,后指针即指向倒数第k个节点
public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode before = dummy;
    while (k-- > 0) {
        before = before.next;
        if (before == null) {
            return null;
        }
    }
    ListNode behind = dummy;
    while (before != null) {
        before = before.next;
        behind = behind.next;
    }
    return behind;
}
func getKthFromEnd(head *ListNode, k int) *ListNode {
    var dummy = ListNode{-1, head}
    var before = &dummy
    for k > 0 {
        before = before.Next
        if before == nil {
            return nil            
        }
        k--
    }
    var behind = &dummy
    for before != nil {
        behind = behind.Next
        before = before.Next
    }
    return behind
}
LeetCode题解 文章被收录于专栏

测试

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:58
点赞 评论 收藏
分享
感觉他们一点都不了解现在这个社会就业有多难,已经在牛客刷到好多篇 延毕的帖子了,延毕就会导致已经找好的工作就没了,还得重新再找,学校和老师们是怎么想的呢????看到学生丢失工作会开心吗 就业数据都在造假,真实的就业困难不去解决 一个个真是好样的
从明天开始狠狠卷JV...:学生看到的是导师不放实习导致offer黄了。 导师看到的是招进来的学生吃自己补助和自己的招生名额,却没给自己升迁带来任何帮助,还要跑路。 根本利益的不一致,最主要留校的导师大概率是职场上招聘失败的,被迫留校的,什么牛鬼蛇神都会有
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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