Insert a node in linked list in sorted manner.

Logic:
sort_addnode(data) function will add the data to linked list
in sorted manner.
for first node ,  It will assign head pointer to it.
After that we are comparing node info with new node's info.
we have maintained Predecessor pointer for our new node.
Look below figure

Sorted manner Insertion

After that it will be easy to add new node.

Read more...

Check whether the given linked list is either NULL-terminated or ends in cycle(cyclic).If there is a cycle find the start node of the list.

To find length of Cycle, we will use Floyd algorithm. We will use http://pakaprogramming.blogspot.in/2014/02/check-whether-given-linked-list-is.html  and extend it.

The total number of red dotted node=length of cycle 

See http://pakaprogramming.blogspot.in/2014/02/check-whether-given-linked-list-is.html

Now follow these steps.

Now we need to compute starting node of loop. So, above logic will perfactly works.

When slow and fast pointer will meet (detect as loop ) at some point in list,

now follow this instructions.

When slowptr==fastptr

- make slowptr=head

-now move slowptr and fastptr one node at time  ( previously fastptr was moving two nodes

at time .Now move it one node at time )

- Again both pointers will meet somewhere. And this point will be starting node of the loop.

(As Fastptr in loop, it will move in loop.So, At some point it has to meet slowptr )

Order Complexity : O(n)

Space Complexity:  O(1)

Read more...

Check whether the given linked list is either NULL-terminated or ends in cycle(cyclic)

Linked List is Cyclic means in linked list any two nodes will be pointing to the same node .We cannot fimd the last node of Cyclic Linked List.

Null terminated Linked Lsit means its last node will be pointing to the NULL.

(a.k.a. Simple Typical Linked List)

NULL Terminated Linked List

Cyclic  Linked List

Logic: We can detect loop in list when we find two notes pointing the 

same node (two node's next address is one node's address).If we find node 

pointing to NULL ,it is NULL terminated List.

Logic1:Brute Force Approach : We point one node and scan entire list if any another node points to that node.It will take O(n^2). But if list contain cycle we can't get end of the list. So, this method won’t work because of Infinite Loop.

Logic 2:Floyd Cycle:

In this algo, We are maintaing two pointers named slow and fast pointer. 

slow pointer moves one node at time while fast node moves two nodes at time

So,IF there is loop, Both pointers will meet at some instant, this can be said 

as there is loop in list. IF anywhere pointer finds node having pointing to NULL, IT can be easily said to be NULL Terminated list.

Order Complexity : O(n)

Space Complexity:  O(1)

Read more...

Find nth node from the end of singly linked list.

We need to find nth node from the end of the list.

nth node from end of linked list

Logic 1: Brute Force Approach

we take one node and count the remaining nodes from it. If it is n then 

it is desired node otherwise we point to next node .

Here we are maintaning two pointers.Thats why it has o(n^2) complexity.

time: O(n^2)

space: O(1)

Logic2: By Length

Here we first find the lenght of linked list say l.

Then we get node l-n+1, which is nth node from last node.

1->2->3->4->5

length is 5.

let say we want 2nd node from last.

So, move_dist=5-2+1=4

so we move upto 4th node from head and after moving , wtever node comes is

our desired node(here 4)

Time: O(n)

Space O(1)

Logic 3:By Two Pointers

we point two pointer to head say t1 and t2. Now we move t1 pointer

upto n move. t2 remains freeze. 

after t1’s move completed, we move both pointer until t1!=NULL.

t2 will point the desired node..

time: O(n)

space O(1)

best complexity:

order Complexity O(n)

space Complexity O(1) 

Read more...