程序员社区

剑指Offer系列(java版,详细解析)22.链表中倒数第K个节点

题目描述

剑指 Offer 22. 链表中倒数第k个节点

难度简单154

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

通过次数135,160

提交次数171,617

节点定义如下:

public class ListNode {
    int val;
    ListNode next = null;
}

测试用例

  • 功能测试(第k个节点在链表的中间;第k个节点是链表的头结点;第k个节点是链表的尾结点)
  • 特殊输入测试(链表头结点为空指针;链表的节点总数少于k;k=0)

题目考点

  • 考查应聘者对链表的理解。
  • 考查应聘者所写代码的鲁棒性

解题思路

假设整个链表有n个节点,那么倒数第k个节点就是从头开始的第n-k+1个节点。

我们定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动;从第k步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1步,当第一个指针到达链表的尾节点时,第二个指针正好指向倒数第k个节点。

但是为了保持程序的鲁棒性,需要考虑下面三个问题:

  1. 输入头节点为空指针
  2. 链表的节点总数少于k
  3. 输入k为0
class Solution {
   
    public ListNode getKthFromEnd(ListNode head, int k) {
   
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
   
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

补充

鲁棒性是指程序能够判断输入是或否合乎规范要求,并对不符合要求的输入予以合理的处理。

容错性 是鲁棒性的一个重要体现。

提高代码的鲁棒性的有效途径是进行防御性编程,防御性编程是一种编程习惯,是指预见在什么地方可能会出现问题,并为这些可能出现的问题制定处理方式。

对于链表的倒数第K个节点都有固定的解法:两个指针,利用 k + (n-(k-1)) = n-1

解题思路

当我们用一个指针遍历链表不能解决问题的时候,可以尝试用两个指针来遍历链表。可以让其他一个指针遍历的速度快一些(比如一次在链表上走两步),或者让它在链表上走若干步。

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 剑指Offer系列(java版,详细解析)22.链表中倒数第K个节点

一个分享Java & Python知识的社区