参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例 1:
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1 输出:[]
示例 3:
输入:head = [1,2], n = 1 输出:[1]
《代码随想录》算法视频公开课::链表遍历学清楚! | LeetCode:19.删除链表倒数第N个节点,相信结合视频再看本篇题解,更有助于大家对链表的理解。
双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路是这样的,但要注意一些细节。
分为如下几步:
-
首先这里我推荐大家使用虚拟头结点,这样方便处理删除实际头结点的逻辑,如果虚拟头结点不清楚,可以看这篇: 链表:听说用虚拟头节点会方便很多?
-
定义fast指针和slow指针,初始值为虚拟头结点,如图:
此时不难写出如下C++代码:
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步,因为需要让slow指向删除节点的上一个节点
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
// ListNode *tmp = slow->next; C++释放内存的逻辑
// slow->next = tmp->next;
// delete tmp;
return dummyHead->next;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//新建一个虚拟头节点指向head
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//快慢指针指向虚拟头节点
ListNode fastIndex = dummyNode;
ListNode slowIndex = dummyNode;
// 只要快慢指针相差 n 个结点即可
for (int i = 0; i <= n; i++) {
fastIndex = fastIndex.next;
}
while (fastIndex != null) {
fastIndex = fastIndex.next;
slowIndex = slowIndex.next;
}
// 此时 slowIndex 的位置就是待删除元素的前一个位置。
// 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
// 检查 slowIndex.next 是否为 null,以避免空指针异常
if (slowIndex.next != null) {
slowIndex.next = slowIndex.next.next;
}
return dummyNode.next;
}
}
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 创建一个虚拟节点,并将其下一个指针设置为链表的头部
dummy_head = ListNode(0, head)
# 创建两个指针,慢指针和快指针,并将它们初始化为虚拟节点
slow = fast = dummy_head
# 快指针比慢指针快 n+1 步
for i in range(n+1):
fast = fast.next
# 移动两个指针,直到快速指针到达链表的末尾
while fast:
slow = slow.next
fast = fast.next
# 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点
slow.next = slow.next.next
return dummy_head.next
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummyNode := &ListNode{0, head}
fast, slow := dummyNode, dummyNode
for i := 0; i <= n; i++ { // 注意<=,否则快指针为空时,慢指针正好在倒数第n个上面
fast = fast.Next
}
for fast != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return dummyNode.Next
}
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
// 创建哨兵节点,简化解题逻辑
let dummyHead = new ListNode(0, head);
let fast = dummyHead;
let slow = dummyHead;
while (n--) fast = fast.next;
while (fast.next !== null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummyHead.next;
};
版本一(快慢指针法):
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let newHead: ListNode | null = new ListNode(0, head);
//根据leetcode题目的定义可推断这里快慢指针均不需要定义为ListNode | null。
let slowNode: ListNode = newHead;
let fastNode: ListNode = newHead;
while(n--) {
fastNode = fastNode.next!; //由虚拟头节点前进n个节点时,fastNode.next可推断不为null。
}
while(fastNode.next) { //遍历直至fastNode.next = null, 即尾部节点。 此时slowNode指向倒数第n个节点。
fastNode = fastNode.next;
slowNode = slowNode.next!;
}
slowNode.next = slowNode.next!.next; //倒数第n个节点可推断其next节点不为空。
return newHead.next;
}
版本二(计算节点总数法):
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let curNode: ListNode | null = head;
let listSize: number = 0;
while (curNode) {
curNode = curNode.next;
listSize++;
}
if (listSize === n) {
head = head.next;
} else {
curNode = head;
for (let i = 0; i < listSize - n - 1; i++) {
curNode = curNode.next;
}
curNode.next = curNode.next.next;
}
return head;
};
版本三(递归倒退n法):
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let newHead: ListNode | null = new ListNode(0, head);
let cnt = 0;
function recur(node) {
if (node === null) return;
recur(node.next);
cnt++;
if (cnt === n + 1) {
node.next = node.next.next;
}
}
recur(newHead);
return newHead.next;
};
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
val pre = ListNode(0).apply {
this.next = head
}
var fastNode: ListNode? = pre
var slowNode: ListNode? = pre
for (i in 0..n) {
fastNode = fastNode?.next
}
while (fastNode != null) {
slowNode = slowNode?.next
fastNode = fastNode.next
}
slowNode?.next = slowNode?.next?.next
return pre.next
}
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
if head == nil {
return nil
}
if n == 0 {
return head
}
let dummyHead = ListNode(-1, head)
var fast: ListNode? = dummyHead
var slow: ListNode? = dummyHead
// fast 前移 n
for _ in 0 ..< n {
fast = fast?.next
}
while fast?.next != nil {
fast = fast?.next
slow = slow?.next
}
slow?.next = slow?.next?.next
return dummyHead.next
}
function removeNthFromEnd($head, $n) {
// 设置虚拟头节点
$dummyHead = new ListNode();
$dummyHead->next = $head;
$slow = $fast = $dummyHead;
while($n-- && $fast != null){
$fast = $fast->next;
}
// fast 再走一步,让 slow 指向删除节点的上一个节点
$fast = $fast->next;
while ($fast != NULL) {
$fast = $fast->next;
$slow = $slow->next;
}
$slow->next = $slow->next->next;
return $dummyHead->next;
}
object Solution {
def removeNthFromEnd(head: ListNode, n: Int): ListNode = {
val dummy = new ListNode(-1, head) // 定义虚拟头节点
var fast = head // 快指针从头开始走
var slow = dummy // 慢指针从虚拟头开始头
// 因为参数 n 是不可变量,所以不能使用 while(n>0){n-=1}的方式
for (i <- 0 until n) {
fast = fast.next
}
// 快指针和满指针一起走,直到fast走到null
while (fast != null) {
slow = slow.next
fast = fast.next
}
// 删除slow的下一个节点
slow.next = slow.next.next
// 返回虚拟头节点的下一个
dummy.next
}
}
impl Solution {
pub fn remove_nth_from_end(head: Option<Box<ListNode>>, mut n: i32) -> Option<Box<ListNode>> {
let mut dummy_head = Box::new(ListNode::new(0));
dummy_head.next = head;
let mut fast = &dummy_head.clone();
let mut slow = &mut dummy_head;
while n > 0 {
fast = fast.next.as_ref().unwrap();
n -= 1;
}
while fast.next.is_some() {
fast = fast.next.as_ref().unwrap();
slow = slow.next.as_mut().unwrap();
}
slow.next = slow.next.as_mut().unwrap().next.take();
dummy_head.next
}
}
/**c语言单链表的定义
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
//定义虚拟头节点dummy 并初始化使其指向head
struct ListNode* dummy = malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = head;
//定义 fast slow 双指针
struct ListNode* fast = head;
struct ListNode* slow = dummy;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;//删除倒数第n个节点
head = dummy->next;
free(dummy);//删除虚拟节点dummy
return head;
}
public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {
ListNode dummpHead = new ListNode(0);
dummpHead.next = head;
var fastNode = dummpHead;
var slowNode = dummpHead;
while(n-- != 0 && fastNode != null)
{
fastNode = fastNode.next;
}
while(fastNode.next != null)
{
fastNode = fastNode.next;
slowNode = slowNode.next;
}
slowNode.next = slowNode.next.next;
return dummpHead.next;
}
}