Given a sorted linked list, how do we delete duplicate nodes from it?
This question is simple and straightforward, we take two pointers, current and next which points the adjacent nodes. In each iteration we compare the values at these two nodes, if they are equal, we delete the node pointed by next and advance the two pointers. Take a look at the following diagram to get better understanding.
This question is simple and straightforward, we take two pointers, current and next which points the adjacent nodes. In each iteration we compare the values at these two nodes, if they are equal, we delete the node pointed by next and advance the two pointers. Take a look at the following diagram to get better understanding.
Here is the C++ implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| struct ListNode | |
| { | |
| int val; | |
| ListNode *next; | |
| }; | |
| ListNode * deleteDuplicates(ListNode *head) | |
| { | |
| if( !head || !(head->next)) | |
| return head; | |
| ListNode *cPtr = head; | |
| ListNode *nPtr = head->next; | |
| while( nPtr ) | |
| { | |
| if( cPtr->val == nPtr->val ) | |
| { | |
| ListNode *temp = nPtr; | |
| nPtr = nPtr->next; | |
| cPtr->next = nPtr; | |
| delete temp; | |
| } | |
| else | |
| { | |
| cPtr = nPtr; | |
| nPtr = nPtr->next; | |
| } | |
| } | |
| return head; | |
| } | |
| int main() | |
| { | |
| ListNode *head = new ListNode(); | |
| head->val = 1; | |
| head->next = new ListNode(); | |
| head->next->val = 1; | |
| head->next->next = NULL; | |
| head = deleteDuplicates(head); | |
| return 0; | |
| } |
by