1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 22 题] “链表中倒数第k个结点”做题记录.md

[剑指 Offer 第 2 版第 22 题] “链表中倒数第k个结点”做题记录.md

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

传送门:AcWing:链表中倒数第 k 个节点牛客网 online judge 地址

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

注意:

  • k >= 0;
  • 如果 k 大于链表长度,则返回 NULL;

样例:

输入:链表:1->2->3->4->5k=2

输出:4

分析:设置快慢指针,思路很简单,不过在具体编码的时候,还是有一些细节要注意的,特别是空指针的判断上。

  • 因为第 k 个结点很可能是链表的第 1 个结点,因此设置虚拟头结点,是这一列问题的基本做法,可以减少分类讨论的情况。
  • 对一些极端情况的讨论(下面代码中的注意点 2 )。

思路1:先遍历完,数出链表有多少个结点。

Python 代码:

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution(object):
        def findKthToTail(self, pListHead, k):
            """
            :type pListHead: ListNode
            :type k: int
            :rtype: ListNode
            """
            if pListHead is None:
                return None
            counter = 0
            p = pListHead
            while p:
                counter += 1
                p = p.next
            if k > counter:
                return None
            p = pListHead
            for _ in range(counter - k):
                p = p.next
            return p

思路2:推荐,设置快慢指针,快指针先走 k-1 步,然后快慢指针一起走。

C++ 代码:

liwei201910116_1.png

Python 代码:

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution(object):
        def findKthToTail(self, pListHead, k):
            """
            :type pListHead: ListNode
            :type k: int
            :rtype: ListNode
            """
            if pListHead is None:
                return None
            fast = pListHead
            # 要注意的临界点1:
            for _ in range(k - 1):
                fast = fast.next
                # 注意判断
                if fast is None:
                    return None
            slow = pListHead
            # 要注意的临界点2:
            while fast.next:
                slow = slow.next
                fast = fast.next
            return slow

Java 代码:

  class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {

        public ListNode FindKthToTail(ListNode head, int k) {
            // 注意点1:极端输入,直接输出结果
            if (head == null) {
                return null;
            }
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
            ListNode fast = dummyNode;
            for (int i = 0; i < k; i++) {
                fast = fast.next;
                // 注意点2:对不符合要求的输入的判断
                if (fast == null) {
                    return null;
                }
            }
            ListNode slow = dummyNode;
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 22 题] “链表中倒数第k个结点”做题记录.md

链接:https://www.javajike.com/article/3271.html

« [剑指 Offer 第 2 版第 21 题] “调整数组顺序使奇数位于偶数前面”做题记录
[剑指 Offer 第 2 版第 23 题] “链表中环的入口结点”做题记录»

相关推荐

QR code