面试题 02.02. 返回倒数第 k 个节点

Posted on | In
Words count in article: 148 | Reading time ≈ 1

题目

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

示例1：

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

提示：

给定的 k 保证是有效的。

解法

解法一：

双指针，p1，p2同时指向head。p2先向前移动k步，然后p1，p2一起向前移动，直到p2到达链表末尾，返回p1的值即可

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int kthToLast(ListNode head, int k) {
        ListNode p1 = head;
        ListNode p2 = head;
        while (k > 0) {
            p2 = p2.next;
            k--;
        }

        while (null != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1.val;
    }
0%