Single Link List

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]

`// 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]

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]

Problem You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2) Output: 8 -> 0 -> 8 [Read More]