237、删除链表

[删除链表][https://leetcode.cn/problems/delete-node-in-a-linked-list/]

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

  • 给定节点的值不应该存在于链表中。
  • 链表中的节点数应该减少 1。
  • node 前面的所有值顺序相同。
  • node 后面的所有值顺序相同。

用后面的值代替前面的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* next = node->next;
        ListNode* cur = node;
        cur->val = next->val;
        cur->next = next->next;
        
    }
};

19、 删除链表的倒数第N个节点

[删除链表的倒数第N个节点][https://leetcode.cn/problems/remove-nth-node-from-end-of-list/submissions/424578279/]

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

先让右指针走n步

再让左右一起走

最后左指针即为倒数第n个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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* dummy = new ListNode(-1, head);
        ListNode* r = dummy;
        ListNode* l = dummy;
        while(n --){
            r = r->next;
        }
        while(r->next){
            r = r->next;
            l = l->next;
        }
        // cout << l->val << endl;
        l->next = l->next->next;
        return dummy->next;

    }
};

83、 删除排序链表中的重复元素

[删除排序链表中的重复元素][https://leetcode.cn/problems/remove-duplicates-from-sorted-list/]

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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) {
        ListNode* cur = head;
        if(head == nullptr){
            return head;
        }
        while(cur->next){
            if(cur->val == cur->next->val){
                cur->next = cur->next->next;
            }else{
              cur = cur->next;
            }
        }
        return head;
    }
};

82、 删除排序链表中的重复元素2

[删除排序链表中的重复元素2][https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/]

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

让右节点先走，如果右节点有重复，则跳过这个右节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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 head;
        }

        ListNode* dummy = new ListNode(-101, head);
        ListNode* l = dummy;
        ListNode* r = head;
        int flag = 0;
        while(r){
            if(r->next && r->val == r->next->val){
                r->next = r->next->next;
                flag = 1;
                continue;
            }
            if(flag == 1){
                flag = 0;
                l->next = r->next;
                r = r->next;
                continue;
            }
            l = l->next;
            r = r->next;
        }
        return dummy->next;
    }
};