LeetCode 图解 | 19.删除链表的倒数第N个节点

点击上方蓝字设为星标

今天分享的题目来源于 LeetCode 上第 19 号问题：删除链表的倒数第N个节点。

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

题目解析

直接来思考如何通过 一次遍历 来解决问题。

由于只允许一次遍历，所以不能用一次完整的遍历来统计链表中元素的个数，而是遍历到对应位置就应该移除了。

那么就需要用两个指针来帮助解题，pre 和 cur 指针。

首先通过一个循环，让 cur 指针 先 向前走 N 步，如果此时 cur 指向空，说明 N 为链表的长度，则需要移除的为首元素，那么此时返回 head->next 即可。

如果 cur 存在，再继续往下走，此时 pre 指针也跟着走，直到 cur 为最后一个元素时停止，此时 pre指向要移除元素的前一个元素，再修改指针跳过需要移除的元素即可。

动画理解

参考代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = dummy;

        for (; n > 0 && pre.next != null; --n) cur = cur.next;

        if (n != 0) return dummy.next;

        while (cur.next != null) {
             pre = pre.next;
             cur = cur.next;
        }
        pre.next = pre.next.next;
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(k)。

• 空间复杂度：O(1)。

相关题目推荐

• LeetCode 26：删除排序数组中的重复项

• LeetCode 203：移除链表元素