Leetcode 237. 删除链表中的节点
问题:有一个单链表的head
,我们想删除它其中的一个节点node
。给你一个需要删除的节点 node
。你将 无法访问 第一个节点head
。链表的所有值都是唯一的,并且保证给定的节点 node
不是链表中的最后一个节点。删除给定的节点。注意,删除节点并不是指从内存中删除它。这里的意思是:
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
node
前面的所有值顺序相同。node
后面的所有值顺序相同。
自定义测试:
- 对于输入,你应该提供整个链表
head
和要给出的节点node
。node
不应该是链表的最后一个节点,而应该是链表中的一个实际节点。 - 我们将构建链表,并将节点传递给你的函数。
- 输出将是调用你函数后的整个链表。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
算法:把 node 的下一个结点复制过来,然后 delete 下一个结点。
代码:
class Solution {
public:void deleteNode(ListNode* node) {*node = *node->next;}
};
class Solution {
public:void deleteNode(ListNode* node) {auto nxt = node->next;*node = *nxt;delete nxt;}
};
Leetcode 19. 删除链表的倒数第 N 个结点
问题:给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
/*** 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) {}* };*/
算法:设置哨兵结点 dummy ,双指针。让右指针 right 先向右走 n 步,然后左右指针一起向右走,当右指针指向最后一个结点时,左指针 left 刚好指向倒数第 n 个。
代码:
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode dummy{0,head};// 哨兵结点(当头结点有可能被删除时设置)auto left = &dummy,right = &dummy;// 双指针while(n--) right = right->next;// 让右指针right先走n步while(right->next){// 左右指针一起走left = left->next;right = right->next;}auto nxt = left->next;left->next = left->next->next;delete nxt;return dummy.next;}
};
Leetcode 83. 删除排序链表中的重复元素
问题:给定一个已排序的链表的头head
, 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
/*** 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* deleteDuplicates(ListNode* head) {if(head == nullptr) return nullptr;auto cur = head;while(cur->next){if(cur->next->val == cur->val){auto nxt = cur->next;cur->next = nxt->next;delete nxt;}else cur = cur->next;}return head;}
};
Leetcode 82. 删除排序链表中的重复元素 II
问题:给定一个已排序的链表的头head
, 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回已排序的链表 。
/*** 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) {}* };*/
算法:遇到相同元素值的结点,全部删除。新建变量 val 存储重复出现的元素值,一旦有结点的值与变量 val 相等,则删除。
代码:
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode dummy(0,head);auto cur = &dummy;while(cur->next && cur->next->next){int val = cur->next->val;if(val == cur->next->next->val){while(cur->next && cur->next->val == val){// 只要一样就一直删除auto nxt = cur->next;cur->next = nxt->next;delete nxt;}}else cur = cur->next;// 删除完就跳到下一个位置}return dummy.next;}
};