训练计划 II

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

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

/*
 * 思路：
 * 1. 将链表转换为 ArrayList。
 * 2. 使用 ArrayList 的 get 方法获取倒数第 cnt 个元素。
 */

import java.util.*;

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

public class Solution {
    public int findNthFromEnd(ListNode head, int cnt) {
        List<ListNode> list = new ArrayList<>();
        ListNode current = head;
        // 将链表转换为列表
        while (current != null) {
            list.add(current);
            current = current.next;
        }
        // 使用列表的 get 方法获取倒数第 cnt 个元素
        return list.get(list.size() - cnt).val;
    }
}

解释

方法:

此题解采用的是快慢指针的技术来找到链表中的倒数第k个节点。首先，定义两个指针s（慢指针）和f（快指针），均指向链表的头节点。首先移动快指针f，让其向前移动k个节点。此时，快慢指针之间相隔k个节点。接着同时移动快慢两个指针，直到快指针到达链表的末尾。此时，慢指针s将指向链表中的倒数第k个节点。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么在快指针f到达链表末尾时，慢指针s的下一个节点就是倒数第k个节点而不是s节点本身？

▷

当快指针f先移动k步后，慢指针s开始从头节点出发移动。此时两个指针之间保持k个节点的距离。当快指针f到达链表的末尾节点时（即f.next为None），慢指针s正好停在倒数第k+1个节点上，因此s的下一个节点（s.next）是倒数第k个节点。这是由快慢指针之间的相对位置决定的。

🦆

在快慢指针方法中，如果链表长度正好等于k，返回的是头节点，但是否应该检查头节点后是否还有其他节点？

▷

在这种情况下，不需要检查头节点后是否还有其他节点。如果链表长度正好等于k，根据题目要求找倒数第k个节点，该节点就是头节点本身，无论链表后面是否还有其他节点。因为快指针移动k步后将指向None，这标志着链表末尾，慢指针正好指向头节点。

🦆

代码中提到如果链表为空直接返回None，但是否还需要处理k值非法（如大于链表长度或为负数）的情况？

▷

是的，确实需要处理k值非法的情况。如果k为负数，这在逻辑上没有意义，需要返回None或抛出异常。如果k大于链表长度，快指针在尝试移动k步时会因为找不到足够的节点而指向None，这种情况应当在代码中进行检查，并作出相应处理（返回None或错误信息），避免运行时错误。

🦆

题解中提到快指针首先移动k步，如何确保在链表长度小于k的情况下不会发生访问空指针的错误？

▷

为了确保不会在链表长度小于k的情况下访问空指针，应在快指针移动过程中检查其是否为None。如果在完成k步移动之前快指针变为None，这意味着链表长度小于k。此时应停止操作并根据具体情况处理，比如返回None或抛出异常。这种检查可以确保代码的健壮性和错误处理的正确性。

训练计划 II

题目描述

代码结果

解释

代码细节讲解

相关问题