LeetCode 19 Remove Nth Node From End of List
题目分析
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
直接法
首先遍历一遍得到总长度，第二次遍历的时候就知道所在的节点的序号了。
快慢指针
虽说这道题挺简单的，但是不小心的话还是有可能没办法 one pass：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head);
ListNode* l = &dummy;
ListNode* r = &dummy;
for (int i = 1; i <= n; i++) {
r = r->next;
}
while (r && r->next) {
r = r->next;
l = l->next;
}
if (l->next) {
l->next = l->next->next;
} else {
l->next = nullptr;
}
return dummy.next;
}
};
之前做这道题时的实现，更加干净：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *fast = head, *slow = head;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
if (!fast) return head->next;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
};