【剑指offer】面试题22：链表中的倒数第k个节点

谁践踏了优雅 2022-06-12 09:45 114阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

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

## 思路 ##

定义两个节点node1，node2  
让node1一开始指向第k个节点，node2指向第1个节点  
此时node1和node2同时前进，\[node1, node2\]区间一共有k个节点  
当node1指向最后一个节点时，node2即指向倒数第k个节点

## 代码 ##

public static class ListNode {
        public int val;
        public ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
    
    public static ListNode FindKthToTail(ListNode head, int k) {
        if(head == null || k <= 0)
            return null;
    
        ListNode node1 = head;
        ListNode node2 = head;
        for(int i = 0; i < k - 1; ++i) {
            node1 = node1.next;
            if(node1 == null)
                return null;
        }
    
        while(node1.next != null) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node2;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
        test3();
    }
    
    /**
     * 功能测试
     * 1-2-3-4-5
     */
    private static void test1() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
    
        ListNode n1 = _22_KthNodeFromEnd.FindKthToTail(node1, 1);
        MyTest.equal(n1, node5);
        ListNode n2 = _22_KthNodeFromEnd.FindKthToTail(node1, 3);
        MyTest.equal(n2, node3);
        ListNode n3 = _22_KthNodeFromEnd.FindKthToTail(node1, 5);
        MyTest.equal(n3, node1);
    }
    
    /**
     * 边界测试
     */
    private static void test2() {
        ListNode node1 = new ListNode(1);
        ListNode n1 = _22_KthNodeFromEnd.FindKthToTail(node1, 1);
        MyTest.equal(n1, node1);
    }
    
    /**
     * 极端测试
     * 1.链表为null
     * 2.k为0
     * 3.k为负数
     * 4.k大于链表长度
     */
    private static void test3() {
        ListNode n1 = _22_KthNodeFromEnd.FindKthToTail(null, 1);
        System.out.println(n1 == null);
    
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
    
        ListNode n2 = _22_KthNodeFromEnd.FindKthToTail(node1, 0);
        System.out.println(n2 == null);
        ListNode n3 = _22_KthNodeFromEnd.FindKthToTail(node1, -1);
        System.out.println(n3 == null);
        ListNode n4 = _22_KthNodeFromEnd.FindKthToTail(node1, 6);
        System.out.println(n4 == null);
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews