CareerCup

here the few cases i can think of

1. Length of both the link lists must be same
2. first of all check that initial list contained loop or not because in that case our sorting will fail
3. pick first element from the link list this should be less than all the remaining elements in a list
4. and each element in a sorted list should be present in a original list.

Iterate through the sorted list starting from head1. at each step compute the difference of the current value with the previous node value. if the value is -ve proceed till the end. If the difference is positive, then the list is not sorted; break and return false. O(n) may be!

do not understand the question and hopebasecoder's answser

I agree with Anon. Is the question asking to check if a linked list is sorted or given a linked list - sort it ?
In the latter case, I think the best bets are selection or insertion sort.

I think i am checking all the conditions in my code..If you think any error in it pls comment abt that:)

bool testlinkedlistsort(node *head1,node *head2)
{
if(head1==NULL && head2==NULL) //If both are NULL return true
return true;
if(head1==NULL || head2==NULL)  //If one of them is NULL then return false
return flase;
/* check for loop in first ll */
node *first,*second;
first=second=head;                     
while(1)
{
if(first==NULL || second ==NULL)
break;
if(second->next==first) 
return false;                    //If there is a loop in first ll return false
first=first->next;
second=second->next->next;
}

while(head)
{
int d=head->data;
int min=INF;
node *tmp=head1;
node *tmp1;
while(tmp)
{
if(tmp->data<min)
{
min=tmp->data;
tmp1=tmp;
}
tmp=tmp->next;
}
if(min!=d)
return false;          //If there any element of sorted list does not present in
                       //unsorted list then return FALSE
tmp1->data=INF;
head=head->next;
}

return true;          //return true if it reaches till here
}

Sort the list with the head pointer and compare it with the linked list with head1 pointer. This way you can test in O(nlogn) time complexity.

1.Check every node present in unsorted List(head poiting) is in place in the sorted Lint(I mean in between less value and grater value nodes).
a.If in Place,move to next node in Unsorted List and check whether it is less than or greater than with previous value.
i.If less value then check in First Half of Sorted List(Like Binary Searching) by repeating Step 1.
b.If Not in Place head1 pointing List is not in sorted Order.

1.take the unsorted linked list and construct a heap from it o(nlogn);
2.traverse the sorted list and at each stage pop the leat element from heap and cmpare it wid the one in the list o(nlogn). so it can be done in time o(nlogn).but with some memory of o(n).

@shambhu - If theres a cycle in the link list then u will never hit a Null. In that cse ur code will go into infinite loop at the start itself where ur waiting for null. ALso if u do hit null for both , then u need not check for cycles!

another method that is possible is for each node in unsorted list search that node into sorted list and delete that node (if found )otherwise return false...
searching in sorted list can be done in logn(binary search is it possible ) and for n node it will be O(nlogn) complexity
and at the last if u r at the end of unsorted list and if elements are there in sorted list then return false else return true ...

please comment if i m wrong

How about this code: This will work if there are no cycles/loops.

If the elements in l1 and l2 are the same, xor of all the elements in the list (in any order) should result in 0.

To see if l2 is in increasing order (better to confirm if the ordering of the elements in the list), then keep a variable 'min' which is initialized to the first element of l2. At the end of the loop if the first element is still the min, xor is 0, then l1 == l2 and l2 is sorted.

int checkListSorting(NODE_PTR l1, NODE_PTR l2)
{
int xor = 0;
NODE_PTR t1 = l1;
NODE_PTR t2 = l2;

int min = l2->val;

while(t1 && t2) {
xor = xor ^ t1->val ^ t2->val;

t1 = t1->next;
t2 = t2->next;

if(t2 && min > t2->val) {
min = -1;
break;
}
}

if(min != -1 && min == l2->val && xor == 0) {
return 1;
}
else {
return 0;
}
}


Comments are welcome!

I would just summarize my approach for the solution. We need to ensure here that all the elements of head is in head1. Apart from various checks that people have done, I add following check which will ensure that both the lists have same elements.

1) Both the lists should have same number of elements. (Suggested above)
2) Sum of all the elements in head and head1 should be same. (to check all the elements of head are in head1.)

It has to be more than a co-incidence if a mistake still happens even after these two checks. What you think?