LeetCodeDay11
2018-04-20 本文已影响0人
GoMomi
237. 删除链表中的节点
描述
- 请编写一个函数,使其可以删除某个链表中给定的(非末尾的)节点,您将只被给予要求被删除的节点。
示例
- 假设该链表为 1 -> 2 -> 3 -> 4,给定您的为该链表中值为3的第三个节点,那么在调用了您的函数之后,该链表则应变成 1 -> 2 -> 4 。
思路
- 只给出了待删除的节点,没有给头节点,因此只能拿到删除节点的后续节点。
- 将后续节点复制到当前节点,然后删除后续节点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution_237 {
public:
void deleteNode(ListNode* node) {
if (node == NULL) return;
ListNode* nextNode = node->next;
if (nextNode) {
node->val = nextNode->val;
node->next = nextNode->next;
free(nextNode);
}
}
};
19. 删除链表的倒数第N个节点
描述
- 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例
- 给定一个链表: 1->2->3->4->5, 和 n = 2.
- 当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明
给定的 n 保证是有效的。
进阶
你能尝试使用一趟扫描实现吗?
思路
- 直观解法,倒数第n个即是正数第Size-n+1个。先遍历出长度,在遍历找到要删除的节点,总共需遍历两次。
- 遍历优化二,空间换时间。维系一个Vector保存遍历过的每个节点。这样遍历过一次后就能直接找出倒数第n个进行移除。
- 最优解,利用两个相隔n的指针。第一个指针向后先走n步,然后两个指针一起走,最后当前序指针走到末端后,后续指针即为所求。
Tips
- 利用一个指向头结点的节点来保证每个节点都有前向节点。一方面可以避免处理删除头结点的问题,另一方面可以从指向头结点的节点开始遍历,避免找到删除节点后,找不到对应的前序节点进行删除操作。(注意此时后续指针的下一个节点才为所求)
- 单向链表中删除一个节点,其实就是要找到它的前序节点,即node->next为所求。这样便于删除操作。
class Solution_19_01 {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == NULL) return NULL;
int size = 0;
ListNode* tmp = head;
while (tmp) {
++size;
tmp = tmp->next;
}
if (n > size) return NULL;
ListNode* pre = NULL;
ListNode* node = head;
ListNode* next = head->next;
for (int i = 1; i < size - n + 1; ++i) {
pre = node;
node = next;
next = next->next;
}
ListNode* newHead = (node == head ? head->next : head);
if (pre) {
pre->next = next;
free(node);
}
return newHead;
}
};
class Solution_19_02 {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == NULL) return NULL;
vector<ListNode*> lists;
ListNode* tmp = head;
while (tmp) {
lists.push_back(tmp);
tmp = tmp->next;
}
ListNode* pre = lists.size() == n ? NULL : lists[lists.size() - n - 1];
ListNode* node = lists[lists.size() - n];
ListNode* newHead = (node == head ? head->next : head);
if (pre) {
pre->next = node->next;
free(node);
}
return newHead;
}
};
// 利用一个指向头结点的节点来保证每个节点都有前向节点,避免处理删除头结点的问题
class Solution_19_03 {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* tag = new ListNode(0);
tag->next = head; // 构建一个指向头结点的节点
ListNode* tmp = tag;
for (int i = 0; i < n; ++i) {
head = head->next;
}
while (head != NULL) {
head = head->next;
tmp = tmp->next;
}
// tmp节点的下一个为要删除的节点
tmp->next = tmp->next->next;
return tag->next;
}
};