Given a sorted linked list, We have to delete all the duplicates in that list. For example, If we get the following list
1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4 -> 5
The output should be
1 -> 2 -> 3 -> 4 ->5
To solve this problem we take two pointers current and next, we iterate through the list until the next pointer reaches the end of the list.
In each iteration we compare the data at current and next nodes. If they are equal, we delete the next node, and the next pointer is advanced to the subsequent node. Take a look at the pictorial representation of this step to understand better.
Here is the working code of C++ for this.
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