返回倒数第 k 个节点

难度:

标签:

题目描述

Implement an algorithm to find the kth to last element of a singly linked list. Return the value of the element.

Note: This problem is slightly different from the original one in the book.

Example:

Input:  1->2->3->4->5 和 k = 2
Output:  4

Note:

k is always valid.

代码结果

运行时间: 44 ms, 内存: 14.9 MB

/*
 * 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
 * 
 * 思路：
 * 1. 将链表转换为一个列表。
 * 2. 使用Java Stream API来处理列表并找到倒数第k个节点。
 */

import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public int getKthFromEnd(ListNode head, int k) {
        List<ListNode> list = new ArrayList<>();
        ListNode current = head;
        // 将链表转换为列表
        while (current != null) {
            list.add(current);
            current = current.next;
        }
        // 使用Java Stream API找到倒数第k个节点
        return list.stream()
                    .collect(Collectors.toList())
                    .get(list.size() - k)
                    .val;
    }
}

解释

方法:

此题解采用了双指针方法（快慢指针）。首先，两个指针 f（快指针）和 s（慢指针）都指向链表的头节点 head。然后，快指针 f 先向前移动 k 步。这样，快慢指针之间就保持了 k 个节点的间隔。接着，快慢指针同时向前移动，直到快指针 f 指向链表的末尾（即 f 为 None）。此时，慢指针 s 指向的就是链表中的倒数第 k 个节点。返回该节点的值即可。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在双指针方法中，为什么快指针先移动k步可以确保慢指针最终指向倒数第k个节点？

▷

在双指针方法中，快指针先移动k步的目的是在快指针和慢指针之间创建一个长度为k的间隔。当快指针从头节点开始移动k步后，如果快指针没有到达链表尾部，那么从快指针到链表末尾的距离加上这个k步的距离等于整个链表的长度。此时，如果继续移动快指针和慢指针，每当快指针向前移动一步，慢指针也向前移动一步，保持这个间隔不变。当快指针到达链表末尾节点的下一个位置（即None），慢指针刚好位于从链表末尾数起的第k个节点，因为从慢指针到链表末尾的距离加上k（慢指针到快指针的距离）等于链表总长度。

🦆

如果快指针在移动k步过程中遇到链表结尾（比如k大于链表长度），这种情况下该如何处理？

▷

如果在移动快指针的过程中k步时快指针到达了链表的末尾，这通常意味着k大于或等于链表的长度。在这种情况下，程序应该进行额外的检查来处理这种情况，避免出现空指针异常。典型的处理方式是，首先在移动快指针之前检查k与链表长度的关系，如果k大于链表长度，可以返回一个错误信息或特殊值，或者根据实际需求可能需要返回链表的第一个节点（如果考虑倒数第k个节点是从1开始计数的话）。

🦆

为什么在快指针到达链表末尾时，慢指针恰好指向倒数第k个节点？能否详细解释其中的逻辑关系？

▷

这个逻辑关系基于快慢指针之间维持的固定距离k。当快指针先行移动k步之后，快慢指针之间的距离就固定为k。当快指针继续移动，慢指针也开始移动，但这个距离始终保持不变。因为快指针从链表头部移动到链表尾部的下一个位置（即None）需要的步数等于链表的长度n。此时慢指针也从头部向前移动了n-k步。因此，慢指针现在的位置就是从链表头部开始的第n-k+1个位置，这也正是整个链表的倒数第k个位置。

返回倒数第 k 个节点

题目描述

代码结果

解释

代码细节讲解

相关问题