Link list ADT
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
What is linked list?
Linked List consists of a sequence of nodes. These nodes are made-up of the following:
A Data Field for housing the data item
One or Two Reference/s for pointing at other node/s i.e. pointing to the next/previous node/s.
In this data structure, the nodes are allowed to be inserted and removed at any point in the list in constant time, however random access in not possible.
[Read More]Calculate length of the linked list that contains loop
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
In previous posts (Loop in a linked list and Calculate node that causes loop in a linked list) we discussed how to detect loop in a linked list and how to calculate node that causes loop in a linked list. In current post we discuss how to calculate length of the linked list when there is a loop in the linked list.
Following procedure explains how to calculate length of the linked list that contains loop:
[Read More]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]Finding the Start of a Loop in a Linked List
Posted on December 27, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Fantastic explanation. Thanks a lot.
crazybuddy - Feb 6, 2015
Fantastic explanation. Thanks a lot.
Thank you :)
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]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
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]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]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]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]