19. 删除链表的倒数第 N 个结点
题目描述
给你一个链表，删除链表的倒数第 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]
提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
解题方法
- C
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = head; // 定义哑节点 int len = 0; if (NULL == head) { return head; } while (head) { head = head->next; len++; // 计算链表长度 } struct ListNode* cur = dummy; for (int i = 1; i < len - n + 1; i++) { cur = cur->next; // 找到要移除的节点 } cur->next = cur->next->next; // 移除节点 struct ListNode* res = dummy->next; free(dummy); // 释放内存 return res; }
复杂度分析
时间复杂度为 O(L)，其中 LLL 是链表的长度。
空间复杂度为 O(1)。
- C 快慢指针
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = head; // 定义哑节点 dummy->val = 0; struct ListNode* fast = head; // 定义双指针 struct ListNode* slow = dummy; for (int i = 0; i < n; i++) { fast = fast->next; // 快指针先移动 n 个节点 } while (fast) { fast = fast->next; // 同步移动，直到快指针到达末尾 slow = slow->next; } slow->next = slow->next->next; // 移除节点 struct ListNode* res = dummy->next; free(dummy); // 释放内存 return res; }
复杂度分析
时间复杂度为 O(L)，其中 LLL 是链表的长度。
空间复杂度为 O(1)。
