LeetCode偶尔一题 —— 19. 删除链表的倒数第N个节点

题目描述

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

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

简单的思路

用一个数组保存所有的链表节点,遍历完之后可以知道倒数第 n 个链表节点。
时间复杂度O(k)空间复杂度O(k),这里 k 为链表长度。

进阶

使用两个指针,快指针先遍历 n 个节点,之后两个指针再一起遍历,等到快指针遍历结束后,慢指针指向的当前节点就是倒数第 n 个节点。
时间复杂度O(k)空间复杂度O(1),这里 k 为链表长度。

⚠️注意:为了写代码方便,我们可以在链表头节点前加多一个节点。

示例代码:

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let temp = { next: head }
temp.next = head
let p = q = temp
for (let i = 0; i <= n; i++) {
p = p.next
}
while(p) {
p = p.next
q = q.next
}
q.next = q.next.next
return temp.next
};

原题地址: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
代码不定时更新,欢迎 star 我的 repo