[LeetCode]19. 删除链表的倒数第N个节点(Remove Nth Node From End of List)

题目描述

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

示例:

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

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

说明:

给定的 n 保证是有效的。

进阶:

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

解题思路

  1. 解法一:队列。使用固定 size 的队列存储一个滑动窗口,相当于用空间换时间;
  2. 解法二:双指针。先让一个指针走 n+1 步,第二个指针再开始走,等第一个指针走完时,第二个指针刚好对应要删除节点的前驱节点。使用了 trick:在原始链表头加一个虚拟节点,可以少判断一些边界条件。

代码

Python 3.6

解法一:队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if head is None:
return None
queue = []
cur = head
while cur is not None:
queue.append(cur)
cur = cur.next
if len(queue) > n + 1:
# 保存 n+1 个,包括前一个节点
queue.pop(0)
if len(queue) == n:
return head.next
if n == 1:
queue[-2].next = None
return head
delete = queue[1]
tmp = delete.next
delete.val = tmp.val
delete.next = tmp.next
del tmp
return head

执行用时 : 92 ms
内存消耗 : 13.7 MB

解法二:双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
p1, p2 = dummy, dummy
count = 0
while p1 is not None:
p1 = p1.next
count += 1
if count > n + 1:
p2 = p2.next
p2.next = p2.next.next
return dummy.next

执行用时 : 60 ms
内存消耗 : 13.9 MB