Sponsored
Sponsored
This approach uses two pointers to traverse the linked list. It compares the current node with the next node. If they have the same value, update the next pointer of the current node to skip the duplicate. Otherwise, move to the next node. This ensures that each element appears only once while maintaining the sorted order.
Time Complexity: O(n), where n is the number of nodes in the list, since we traverse each node once.
Space Complexity: O(1), as no additional space is used apart from a few pointers.
1#include <stdlib.h>
2
3struct ListNode {
4 int val;
5 struct ListNode *next;
6};
7
8struct ListNode* deleteDuplicates(struct ListNode* head) {
9 struct ListNode* current = head;
10 while (current != NULL && current->next != NULL) {
11 if (current->val == current->next->val) {
12 struct ListNode* toDelete = current->next;
13 current->next = current->next->next;
14 free(toDelete);
15 } else {
16 current = current->next;
17 }
18 }
19 return head;
20}
21This C code defines a function to delete duplicates from a sorted linked list. It uses a single while loop to traverse the list, comparing the value of the current node with the next node. If they match, the next pointer is adjusted to skip the duplicate, effectively deleting it. Memory for the deleted node is freed to avoid leaks.
This approach employs recursion to solve the problem. The base case checks if the current node is null or has no next node. For other cases, if the current node and the next node have the same value, the next pointer is adjusted to the result of the recursion call. Otherwise, move to the next node using recursion.
Time Complexity: O(n), where n is the number of nodes, each node is visited once.
Space Complexity: O(n), due to recursion stack space.
1
This C function utilizes recursion to remove duplicate nodes. It recursively processes nodes, checking if current and next nodes have the same value, and adjusts the pointers accordingly, freeing memory for duplicate nodes.