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]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]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]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)); } }
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); }
Middle of a linked list
Posted on April 8, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Find the middle node of the linked list.
Follow up - How will you get it in first pass.
Solution Method 1 - Get the length and travel to middle
Traverse the whole linked list and count the no. of nodes. Now traverse the list again till count/2 and return the node at count/2.
Method 2 - Uses one slow pointer and one fast pointer
Traverse linked list using two pointers.
[Read More]Basic functions of link list - Add and print
Posted on April 8, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
`// Function to add new nodes to the linked list
void add(node * head , int value)
{
temp = (mynode *) malloc(sizeof(struct node));
temp->next=(mynode *)0;
temp->value=value;
if(head==(mynode *)0)
{
head=temp;
tail=temp;
}
else
{
tail->next=temp;
tail=temp;
}
}`
`// Function to print the linked list…
*void print_list(struct node head)
{
mynode *temp;
printf("\n[%s] -> “, listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->”,temp->value);
}
printf(“NULL\n”);
}`
Similar code in java:
[Read More]Function to add node to double link list
Posted on April 8, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
**2 struct pointers (Double link list)**
typedef struct node { int value; struct node *next; struct node *prev; }mynode ;
`// Function to add a node
void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(*head == NULL)
{
head=temp;
temp->value=value;
}
else
{
for(cur=head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}`
Detecting a loop in a linked list
Posted on April 8, 2010
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem : Given a singly linked list, find if there exist a loop.
Example
A -> B -> C -> D -> E -> C [ E again point to C]
Solutions
Method 1 - Using hashing
Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.
[Read More]Comparing floats
Posted on April 8, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
int main()
{
float me = 1.1;
double you = 1.1;
if(me==you)
printf(“I love U”);
else
printf(“I hate U”);
}
Output - I hate U
Explanation
For floating point numbers (float, double, long double) the values cannot be predicted exactly. Depending on the number of bytes, the precession with of the value represented varies. Float takes 4 bytes & long double takes 10 bytes. So float stores 0.9 with less precision than long double.
[Read More]