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

简介: 19 删除链表的倒数第 N 个结点

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

中等

相关标签

相关企业

提示

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

这段代码使用了双指针的方法,其中一个指针先走 n 步,然后两个指针一起走,直到第一个指针到达链表末尾,此时第二个指针指向的位置就是要删除的节点。

#include <stdio.h>
#include <stdlib.h>
// 链表节点的定义
struct ListNode {
    int val;
    struct ListNode *next;
};
// 删除链表倒数第n个节点的函数
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // 使用双指针,首先让一个指针先走n步
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *fast = dummy;
    struct ListNode *slow = dummy;
    // 让fast指针先走n步
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }
    
    // 当fast指针到达链表末尾时,slow指针就在倒数第n+1个节点
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    // 删除倒数第n个节点
    struct ListNode *temp = slow->next;
    slow->next = slow->next->next;
    free(temp);
    return dummy->next;
}
// 创建链表节点
struct ListNode* createNode(int val) {
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}
// 打印链表
void printList(struct ListNode *head) {
    struct ListNode *current = head;
    while (current != NULL) {
        printf("%d -> ", current->val);
        current = current->next;
    }
    printf("NULL\n");
}
// 释放链表节点
void freeList(struct ListNode *head) {
    struct ListNode *current = head;
    while (current != NULL) {
        struct ListNode *temp = current;
        current = current->next;
        free(temp);
    }
}
int main() {
    // 创建示例链表:[1, 2, 3, 4, 5]
    struct ListNode *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);
    int n = 2;
    printf("原始链表:");
    printList(head);
    // 删除倒数第n个节点
    head = removeNthFromEnd(head, n);
    printf("删除倒数第%d个节点后的链表:", n);
    printList(head);
    // 释放链表内存
    freeList(head);
    return 0;
}
  1. struct ListNode 定义了链表节点的结构,包含一个整数值 val 和一个指向下一个节点的指针 next
  2. removeNthFromEnd 函数用于删除链表倒数第 n 个节点。它首先创建一个虚拟头节点 dummy,并使用两个指针 fastslow 进行遍历。
  3. createNode 函数用于创建新的链表节点,并返回指向该节点的指针。
  4. printList 函数用于打印链表。
  5. freeList 函数用于释放链表的内存。
  6. main 函数中,首先创建一个示例链表 [1, 2, 3, 4, 5],然后调用 removeNthFromEnd 删除倒数第 n 个节点,并最后打印删除节点后的链表。

在这个代码中,使用了一个虚拟头节点 dummy 的原因是为了简化删除操作的处理。如果不使用虚拟头节点,而直接使用 head,则需要特别处理删除头节点的情况,因为头节点没有前一个节点。这会导致代码中需要额外的条件判断来处理删除头节点的情况,从而增加了复杂性。

通过使用虚拟头节点 dummy,可以确保链表中的每个节点都有一个前一个节点,使得删除操作的处理更加统一和简单。此外,虚拟头节点 dummy 在遍历过程中始终位于链表的开头,不会被删除,因此不会影响最终的结果。

总的来说,使用虚拟头节点 dummy 可以简化代码逻辑,提高代码的可读性和可维护性,尤其是在处理链表的边界情况时。

 

相关文章
|
2天前
查找两个链表的第一个公共结点
查找两个链表的第一个公共结点
9 0
|
3天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
8 0
|
7天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
7天前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
9天前
19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
15 1
|
15天前
|
存储 Java
高效删除链表倒数节点最优实现
要删除链表的倒数第 n 个节点,并返回链表的头节点,我们可以使用一趟扫描的方法来实现。这个方法涉及使用两个指针:快指针和慢指针。
|
15天前
19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
【每日一题】LeetCode——链表的中间结点
【每日一题】LeetCode——链表的中间结点
|
15天前
|
存储
三种方法实现获取链表中的倒数第n个元素
三种方法实现获取链表中的倒数第n个元素
18 0
|
15天前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)