LeetCode题解之返回倒数第 k 个节点

返回倒数第 k 个节点

题目描述

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

示例 :

输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：

给定的 k 保证是有效的。

解题思路

使用双指针法，让第一个指针先向前走 k 步，然后两个指针一起向前走，当第一个指针到达链表末尾的时候，此时第二个指针所在的节点即为链表的倒数第 k 个节点。

复杂度分析

• 时间复杂度：O(n)，其中 n 为链表的长度。
• 空间复杂度：O(1)。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode n1 = head;
        ListNode n2 = head;
        for (int i = 0; i < k; i ++) {
            n1 = n1.next;
        }
        while (n1 != null) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n2.val;
    }
}