Single Link List

Intersection of two sorted lists or 2 sorted arrays

Posted on May 20, 2011 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

For two sorted lists, 1, 2, 12, 15, 17, 18 1, 12, 14, 15, 16, 18, 20 intersection is bold numbers. Solution 1 : Brute force An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. [Read More]

Deleting a middle node from a single linked list when pointer to the previous node is not available

Posted on October 22, 2010 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Problem Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e Solution If we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. [Read More]

kodeknight link list Single Link List CrackingTheCodingInterview

Reverse a linked list

Posted on April 9, 2010 (Last modified on August 7, 2020) | 5 minutes | Kinshuk Chandra

Problem Reverse a linked list. Follow up - Can you do it with only 2 pointers. Solution This is one of the famous interview questions. Following are two procedures to reverse a single linked list: Iterative Procedure Recursive Procedure Iterative solution Method 1 - Iterative Procedure The following are the sequence of steps to be followed: Initially take three pointers: PrevNode, CurrNode, NextNode Let CurrNode point to HeaderNode of the list. [Read More]

kodeknight link list reverse Single Link List

Remove duplicates from a sorted linked list

Posted on April 8, 2010 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Problem : Remove duplicates from a sorted linked list Example Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. Solutions As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There’s a tricky case where the node after the next node needs to be noted before the deletion. // Remove duplicates from a sorted list void RemoveDuplicates(struct node\* head) { struct node\* current = head; if (current == NULL) return; // do nothing if the list is empty // Compare current node with next node while(current->next! [Read More]

kodeknight link list duplicate Single Link List sorting

Insert nodes into a linked list in a sorted fashion

Posted on April 8, 2010 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node. Note that we assume the memory for the new node has already been allocated and a pointer to that memory is being passed to this function. // Special case code for the head end **void linkedListInsertSorted(struct node** headReference, struct node* newNode) ** { // Special case for the head end if (*headReference == NULL || (*headReference)->data >= newNode->data) { newNode->next = *headReference; *headReference = newNode; } else { // Locate the node before which the insertion is to happen! [Read More]

kodeknight link list Single Link List

Return the nth node from the end of a linked list

Posted on April 8, 2010 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem Get the nth element from the end of the linked list Example Lets say the Single Linked List (SLL) is 0-1-2-3-4-5-6-7-8-9, and we want to find last 3rd element (say ‘pos=3′) in this SLL. So, we have to return 7 here. Solutions Method 1 - 2 pointer approach Here is a solution which is often called as the solution that uses frames. Suppose one needs to get to the 6th node from the end in this LL. [Read More]

kodeknight link list Single Link List CrackingTheCodingInterview

Binary search on a linked list

Posted on April 8, 2010 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array? Think hard, real hard. Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. [Read More]

kodeknight link list Single Link List

C program to free the nodes of a linked list

Posted on April 8, 2010 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Before looking at the answer, try writing a simple C program (with a for loop) to do this. Quite a few people get this wrong. This is the wrong way to do it struct list *listptr, *nextptr; for(listptr = head; listptr != NULL; listptr = listptr->next) { free(listptr); } If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next! [Read More]

kodeknight link list Single Link List

Copy of a linked list

Posted on April 8, 2010 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Check out this C program which creates an exact copy of a linked list.

**copy_linked_lists(struct node *q, struct node **s)** { if(q!=NULL) { *s=malloc(sizeof(struct node)); (*s)->data=q->data; (*s)->link=NULL; copy_linked_list(q->link, &((*s)->link)); } }

kodeknight link list Single Link List

Compare two linked lists

Posted on April 8, 2010 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

**int compare_linked_lists(struct node *q, struct node *r)** { static int flag; if((q==NULL ) && (r==NULL)) { flag=1; } else { if(q==NULL || r==NULL) { flag=0; } if(q->data!=r->data) { flag=0; } else { compare_linked_lists(q->link,r->link); } } return(flag); }

kodeknight link list Single Link List