83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Approach : The key to solve the problem is using the right loop condition and maintaining necessary pointers in each loop.

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

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode *cur, *_next; if(head == NULL || head->next == NULL){ return head; } cur = head; while(cur && cur->next){ //set the pointer of the current next to the next node if duplicate is found if(cur->val == cur->next->val){ _next = cur->next->next; free(cur->next); cur->next = _next; }else{ //else just move forward to next node cur = cur->next; } } return head; }

Read More

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Approach : Here is the simple recursive solution to solve the problem:

1. Base case : Return one of the lists if another is NULL
2. Else recursively call the function with appropriate values of two current nodes' values

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* a, struct ListNode* b) {
    struct ListNode* result = NULL;  
   /* Base cases */  
   if (a == NULL)  
     return(b);  
   else if (b == NULL)  
     return(a);  
   /* Pick either a or b, and recur */  
   if (a->val <= b->val) {  
     result = a;  
     result->next = mergeTwoLists(a->next, b);  
   }else {  
     result = b;  
     result->next = mergeTwoLists(a, b->next);  
   }  
   return(result); 
}

Here is the link to the ideone solution : https://ideone.com/V6zDKA

Read More

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

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

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head == NULL || head->next == NULL){ return head; } //create a dummy node to avoid the case of head value getting repeated which is difficult to handle struct ListNode *res = new struct ListNode(0); res->next = head; struct ListNode *cur = res; while(cur->next && cur->next->next){ //if the next value is same as its next value if(cur->next->val == cur->next->next->val){ int val = cur->next->val; //move forward if same value is repeating while(cur->next && cur->next->val == val){ cur->next = cur->next->next; } }else{ cur = cur->next; } } //return next of the dummy node return res->next; } };

Read More

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

This problem involves solution to the reverse linked list problem.

Follow up:

Could you do it in O(n) time and O(1) space?

Approach: Reverse the linked list after the middle and see if the first half is equal to the reversed.

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 40 41 42 43 44 45 46

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL){ return true; } ListNode *slow, *fast; slow = head; fast = head; while(fast->next && fast->next->next){ fast = fast->next->next; slow = slow->next; } ListNode *secondHead = slow->next; slow->next = NULL; //reverse second part of the list ListNode *prev = NULL, *curr, *next = secondHead; while(next){ curr = next; next = next->next; curr->next = prev; prev = curr; } //compare two sublists now ListNode *p = curr; ListNode *q = head; while(p){ if(p->val != q->val) return false; p = p->next; q = q->next; } return true; } };

Read More