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

题目描述

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

image-20221016001835216

image-20221016001841890

思路分析

我们可以使用双指针的方法来解决这个问题。具体步骤如下：

  1. 初始化两个指针：first 和 second，都指向链表的头节点。
  2. 移动第一个指针：让 first 指针先移动 N 步，这样 first 和 second 之间的距离为 N。
  3. 同时移动两个指针：当 first 指针到达链表的末尾时，second 指针正好指向要删除的节点的前一个节点。
  4. 删除节点：修改 second 指针的 next 指向 second.next.next，从而删除倒数第 N 个节点。
  5. 返回头节点：如果删除的是头节点，返回新的头节点。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	first, second := dummy, dummy
	for i := 0; i < n; i++ {
		first = first.Next
	}
	for first != nil && first.Next != nil {
		first = first.Next
		second = second.Next
	}
	second.Next = second.Next.Next
	return dummy.Next
}

🍏 点击查看 Java 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/95413141
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！