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

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

本题来自 LeetCode:19. 删除链表的倒数第 N 个节点[1]

题目详情

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

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:给定的n保证是有效的。
进阶:你能尝试使用一趟扫描实现吗?

题目分析

  1. 本题可以先扫描一遍链表,记录链表的长度length;然后第二遍,就可以扫描到length-n位置,然后将后一位置length - n + 1节点删掉即可;但是这种解法需要扫描两趟链表,不符合进阶要求。
  2. 可以使用双指针(快慢指针),快指针先走n步,然后同时走;
  3. 使用一个空节点做为头节点,可以不用考虑特殊情况,比如 n 等于链表长度(即删除头节点);

题目解答

/**
* 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(-1);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for(int i = 0; i < n; i++) {
fast = fast.next;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;

return dummy.next;
}
}

复杂度分析:
时间复杂度:O(n)
空间复杂度:O(1)

参考资料

[1]

19. 删除链表的倒数第N个节点: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/


原文始发于微信公众号(xiaogan的技术博客):19. 删除链表的倒数第 N 个节点