hi,
i wanna just give some problems of linked list and solutions.
Q.1.)Given a singly-linked, find out the mid point of a single linked list in a
single parse of the list. Assume the program would be loaded in read-only
memory so no manipulation of the list is allowed.
Having two pointers makes easy to implement gettig middle node of a linked list.
while one pointer goes on the whole list the other pointer goes as half as first pinter's.
node_t * get_mid_node( list_t * list ) {
node_t *p, *q;
int counter = 1;
if ( NULL == list ) return NULL;
p = list->head;
q = list->head;
while ( p ) {
p = p->next;
if ( counter++ 2 == 0 ) {
q = q->next;
}
}
return q;
}
Q.2.)Given: 2 Unsorted single linked list
Todo: Fastest and optimised way to merge and make a single sorted list with
these 2 unsorted single linked list.
list_t * get_intersection_of_two_sorted_list ( list_t * list1, list_t * list2 ) {
node_t *first, *second;
list_t *intersection_list;
if ( !list1 || !list2 ) return NULL;
intersection_list = ( list_t * ) malloc( sizeof( list_t ) );
if ( NULL == intersection_list ) {
fprintf(stderr, "Bad memory allocation error\n");
return NULL;
}
while ( first && second ) {
if ( first->data < second->data ) first = first->next;
else if ( second->data < first->data ) second = second->next;
else {
add_list( intersection_list, first->data );
first = first->next;
second = second->next;
}
}
}
Q.3.)Given a linked list, your are asked to find out the nth last element in
the linked-list. (n would be given as the argument to the function)
Last nth element is ( l - n + 1)th element from the beginning, so having two pointers:
- Two pointers indicates the list->head at first
- First pointer goes to nth node from the beginning
- Both pointers goes simultaneously until first pointer comes to the end of the list
- Now second pointer walks ( l - n ) nodes, head node is also assumed one walk for two pointers.
- Then secod pointer now indicates
the last nth element.
Test Cases:
- List is null
- List is empty
- List with length 1 ( get 1 )
- List with length 2 ( get 1, 2 )
- List with length 3 ( get 3, 1, 2 )
- Any value larger than the size of list
int getLastNth( list_t *list, unsigned int n ) {
int counter;
node_t *p, *q;
if ( NULL == list ) {
fprintf( stderr, "list is null...(getLastNth)\n" );
exit(1);
}
p = list->head;
q = list->head;
for ( counter = 0; p && counter < n - 1; p = p->next, counter++ );
if ( NULL == p ) {
fprintf( stderr, "Index is out boundary...(getLastNth)\n" );
exit(1);
}
while ( p->next ) {
q = q->next;
p = p->next;
}
return q->data;
}
Q.4.)Print reverse order of a singly linked list.
void print_list_reverse_order( node_t * head ) {
if ( NULL == head ) return;
print_list_reverse_order( head->next );
printf("%d\n", head->data);
}
