删除链表的倒数第 N 个结点

难度:

标签:

题目描述

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

代码结果

运行时间: 20 ms, 内存: 15.9 MB

/*
 * 思路：
 * 使用 Java Stream API 处理链表有一定难度，因为 Stream API 主要用于处理集合、数组等。链表需要先转换成可处理的集合或数组，然后再进行操作。以下代码展示了如何通过流操作实现目标。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> list = new ArrayList<>();
        ListNode current = head;
        // 将链表转换成列表
        while (current != null) {
            list.add(current);
            current = current.next;
        }
        // 找到要删除的节点
        int indexToRemove = list.size() - n;
        if (indexToRemove == 0) {
            return head.next;
        }
        list.get(indexToRemove - 1).next = list.get(indexToRemove).next;
        return head;
    }
}

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

解释

方法:

这个题解采用了双指针（快慢指针）的方法来找到倒数第n个节点。首先，创建一个哑节点(dummy node)，这个节点的next指向链表的head，这样可以方便地处理边界情况，比如删除链表的头节点。算法首先将一个指针(first)向前移动n次，这样从first到链表末尾就会有n个节点。然后，同时移动两个指针（first和second），直到first指针到达链表末尾。这时，second指针会指向要删除节点的前一个节点。通过修改second的next指向，可以将倒数第n个节点从链表中删除。最后，返回dummy.next，即更新后的链表头节点。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么在删除链表节点时需要使用一个哑节点（dummy node）？

▷

使用哑节点可以简化删除链表头节点的复杂度。没有哑节点，如果需要删除头节点，就必须单独处理这种边界情况，因为头节点没有前一个节点。引入哑节点后，不管是删除头节点还是其他节点，都可以统一通过修改前一个节点的next指针来实现。这样可以使代码更加简洁且易于维护。

🦆

你在算法中如何确保当n等于链表长度时，可以正确删除头节点？

▷

当n等于链表长度时，第一个指针（first）会移动n步达到链表末尾的None。在这种情况下，第二个指针（second）仍然指向哑节点。因为哑节点的next指向原始头节点，移动second的next指针到next的next节点（即second.next = second.next.next）实际上会删除原始的头节点。因此，通过使用哑节点和适当移动第二个指针可以确保即使n等于链表长度时也能正确删除头节点。

🦆

在for循环中，如果链表长度等于n，那么first指针移动n步后会不会变成None，这种情况下如何处理？

▷

是的，如果链表长度等于n，那么first指针移动n步后确实会变成None。在算法中，这种情况是合理的，因为接下来的while循环将不执行，因为first已经是None。这时，second指针位于哑节点位置，其next指向的是原链表的头节点。如前一个问题所述，通过将second.next指向second.next.next，可以删除原链表的头节点。这正是算法处理这种情况的方式。

删除链表的倒数第 N 个结点

题目描述

代码结果

解释

代码细节讲解

相关问题