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题解 文章被收录于专栏

测试

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-06 13:45
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 17:06
黑龙江大学_2024
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议