82. Remove Duplicates from Sorted List II
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3]
Output: [2,3]
Constraints:
- The number of nodes in the list is in the range [0, 300].
- -100 <= Node.val <= 100
- The list is guaranteed to be sorted in ascending order.
From: LeetCode
Link: 82. Remove Duplicates from Sorted List II
Solution:
Ideas:
1. Initialize Pointers and Dummy Node:
- Create a dummy node that acts as a placeholder for the new list. Initialize prev to this dummy node and curr to the head of the original list.
2. Traverse the Original List:
- Go through each node in the list using the curr pointer.
3. Check for Duplicates:
- If the curr node has a duplicate (i.e., curr->val is the same as curr->next->val), move curr to the last duplicate node. This is done using the while loop within the main while loop.
4. Add Unique Nodes to New List:
- If the curr node is not a duplicate, add it to the new list. The prev pointer keeps track of the last node added to the new list.
5. Move to Next Node:
- Move curr to the next node in the original list.
6. Terminate New List:文章来源:https://www.toymoban.com/news/detail-693751.html
- Make sure to set the next of the last node in the new list to NULL.
7. Return New List:文章来源地址https://www.toymoban.com/news/detail-693751.html
- The new list starts after the dummy node. So, we return dummy->next as the new head of the list.
Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head) {
// Create a dummy node to serve as the head of the new list
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = NULL;
// Initialize pointers
struct ListNode* prev = dummy;
struct ListNode* curr = head;
while (curr != NULL) {
// Check if the current node is a duplicate
int duplicate = 0;
while (curr->next != NULL && curr->val == curr->next->val) {
duplicate = 1;
curr = curr->next;
}
// If it's not a duplicate, add it to the new list
if (duplicate == 0) {
prev->next = curr;
prev = curr;
}
// Move to the next node in the original list
curr = curr->next;
}
// Terminate the new list
prev->next = NULL;
// Return the new list (skipping the dummy node)
struct ListNode* newHead = dummy->next;
free(dummy);
return newHead;
}
到了这里,关于LeetCode //C - 82. Remove Duplicates from Sorted List II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!