Add 2 large numbers in the form of list, without reversing the linked lists

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

You are given two numbers in the form of linked list.Add them without reversing the linked lists. linked lists can be of any length.  Take two stacks and push a linked list to a stack. After done pushing, simply start popping the stacks, add the numbers, get the carry over, generate another node with the result and add to front to a new linked list. We have already done this question here, which involves reversal of 2 numbers and then adding it. [Read More]
kodeknight  link list  Single Link List  stack 

Finding the Start of a Loop in a Linked List

 Posted on December 27, 2011  (Last modified on August 7, 2020)  |  9 minutes  |  Kinshuk Chandra

Problem  Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C Example head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ^ | | | +------------------------+ Answer here is 3. [Read More]
kodeknight  link list  java-code  Single Link List  loop  CrackingTheCodingInterview 

Deleting a node in singly linked list if it is less than any of the successor nodes

 Posted on September 26, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Hi, try with 1,7,0,10. output must be 10. but your…

Unknown - Jun 6, 2012

Hi,
try with 1,7,0,10.
output must be 10.
but your algorithm outputs wrong answer

it seems that algo is correct..
1,7,0,10
reverse

10 0 7 1

max_till_here= 10

0 < 10 delete 0

left : 10 7 1

7 < 10 : delete 7

1 < 10 : delete 1

output : 10

kodeknight  link list  Single Link List  delete 

Deleting a node in singly linked list if it is less than any of the successor nodes

 Posted on September 26, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Question : Given a link list of integers delete all nodes which have value smaller than the value of any following node. **Example :**7 4 5 2 3 6 **Output : ** 7 6 Solution: The solution is to : 1. Reverse the list 6 3 2 5 4 7 2. Delete all the elements which are below the max-till-now element. eg. max-till-now=6….Delete all the elements below 6…till you find another max element = max-till-now = 7 [Read More]
kodeknight  link list  Single Link List  delete 

Check if singly linked list is Palindrome

 Posted on September 19, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

There are couple of solution to it : Method 1 - Using the stack A simple solution is to use a stack of list nodes. This mainly involves three steps. Traverse the given list from head to tail and push every visited node to stack. Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node. If all nodes matched, then return true, else false. [Read More]
kodeknight  String  link list  Single Link List  fast pointer  palindrome 

Sum of two long positive numbers (each represented by linked lists)

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

Code : #include <stdio.h> #include <stdlib.h> typedef struct Node { unsigned char c; struct Node \*next; ``` ``` }Node; ``` ``` typedef Node \*slist; ``` ``` slist reverse(slist); Node *makeNode(unsigned char); /* \*/ ``` ``` slist Sum(slist left, slist right) { ``` ``` if(!left || !right) { return left ? left : right; } ``` ``` left = reverse(left); right = reverse(right); unsigned char carry = left->c + right->c; slist ret = makeNode(carry % 10); [Read More]
kodeknight  link list  Single Link List 

Find median of a linked list or a Tree

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

This pseudo-code holds for a Double Linked list: 1. init two pointers one at the start of the list(p1) and the other at the end (p2) 2. if p1=null or p2==null return NONE 3. At each iteration, visit node p1.next and p2.previous 4. if p1.next==p2.previous !=p1 || p2 then middle is obtained for an odd number of nodes. Return result 5. if p1.next==p2.previous=p1|| p2 then middle is for an even number of nodes. [Read More]
median  kodeknight  link list  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]
kodeknight  link list  Single Link List  binary search  two-arrays  two-sorted-arrays  intersection  sorted-array 

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