LeetCode 0019 - Remove Nth Node From End of List
# Hints
- 链表
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a linked list, remove the -th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given will always be valid.
Follow up:
Could you do this in one pass?
# 题意
给定一个链表,给定一个正整数 ,要求将链表从表尾起的第 个节点删除,并返回此时的链表头。输入保证是 合法的。要求只遍历链表一次就解决问题。
# 题解
因为是单链表,我们无法从表尾起反向遍历。一个显然的解决方案是,先遍历一遍链表,求出链表长度 ,那么只要将从表头起的第 个节点删除即可,但这样总共需要遍历链表两次。
至于如何只遍历一次就解决问题,我们考虑用前后指针法,维护两个指针 和 ,令 先前进 步,然后令 同时不断前进,直到 到达表尾为止。因为 的距离为 ,所以此时 所指即为从表尾起的第 个节点,即可完成删除操作。
细节问题:
- 注意特判 等于链表长度的情况,此时需要将 删除并返回
head->next
。一个避免特判的方法是开辟一个临时节点接在 的前面,将其置为新的 ,这样就消除了原本的 的特殊性。但我的代码中并没有用此处理方法,而是直接特判。
# AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode * next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode * next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode * removeNthFromEnd(ListNode * head, int n) {
// 预处理
ListNode * p = head;
ListNode * q = head;
while (n --) {
q = q->next;
}
// 特判
if (q == nullptr) {
// 删除
q = head;
head = head->next;
delete q;
// 返回
return head;
}
// 处理
while (q->next != nullptr) {
p = p->next;
q = q->next;
}
// 删除
q = p->next;
p->next = p->next->next;
delete q;
// 返回
return head;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01