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

2023-12-14 06:05:21

题目描述

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

示例:

输入: 1->2->3->4->5, n = 2
输出: 1->2->3->5

解题思路

使用双指针的方法来找到倒数第 n 个节点,然后删除该节点。

解题步骤

  1. 使用两个指针 fastslow,初始时都指向链表的头节点。
  2. 先将 fast 指针向前移动 n+1 步。
  3. 然后,同时移动 fastslow 指针,直到 fast 指针到达链表末尾。
  4. 此时,slow 指针指向倒数第 n+1 个节点。
  5. slow 指针的下一个节点删除,即将 slow.next 指向 slow.next.next
  6. 返回头节点。

C#代码实现

public ListNode RemoveNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;

    // 先将 fast 指针向前移动 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // 同时移动 fast 和 slow 指针,直到 fast 到达链表末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 删除倒数第 n 个节点
    slow.next = slow.next.next;

    return dummy.next;
}

C代码实现

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* fast = dummy;
    struct ListNode* slow = dummy;

    // 先将 fast 指针向前移动 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }

    // 同时移动 fast 和 slow 指针,直到 fast 到达链表末尾
    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;
}

时间复杂度和空间复杂度

  • 时间复杂度:O(n),其中 n 是链表的长度。两个指针分别遍历链表一次。
  • 空间复杂度:O(1)。除了常数级别的变量,算法的空间复杂度是常数级别的。

文章来源:https://blog.csdn.net/Ammmmmmmmn/article/details/134913434
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。