Linked List

Linked List Concepts

Printing Linked list without traversing the list:

void printreverse(Node *node)
{
if (node)
{
printreverse(node->next);
printf("%d -> ",node->info);
}
}


Reversing the list using stack:
Push all the nodes, pop one by one and print them… Here is the program for this..

void printreverse(Node* node)
{
Node *tmpnode;
Stack *stack = CreateStack();
while(node)
{
Push(stack, node);
node = node->next;
}
tmpnode = Pop(stack);
while(tmpnode)
{
tmpnode = Pop(stack);
printf("%d -> ", tmpnode->info);
}
DestroyStack(stack);
}
Reverse linked list using pointers
Reversing a single list can achieved using a stack very easily. however this can be done without using stack, and by simply using three additional pointers. Let us say we are using curr, next, result pointers, curr points to current node, next obviously points to the next node, result points to the new reversed linked list.
here is the pictorial representation of this operation for better understanding…

now result holds one reversed node, and curr points to the rest of the linked list..

now result holds a pointer to the reversed linked list (reversed two pointers already)…. curr holds rest of the list

we reversed successfully….

here is the routine for doing this…..
void reverse_single_linked_list(struct node** headRef)
{
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL)
{
next = current->next; // tricky: note the next node
current->next = result; // move the node onto the result
result = current;
current = next;
}
*headRef = result;
Question: How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?
Answer: There are a number of approaches. The approach I shared is in time N (where N is the number of nodes in your linked list). Assume that the node definition contains a boolean flag, bVisited.
// error checking and checking for NULL at end of list omitted
p1 = p2 = head;

do {
p1 = p1->next;
p2 = p2->next->next;
} while (p1 != p2);
p2 is moving through the list twice as fast as p1. If the list is circular, (i.e. a cycle exists) it will eventually get around to that sluggard, p1.

Question: How would you reverse a doubly-linked list?
Answer: This problem isn't too hard. You just need to start at the head of the list, and iterate to the end. At each node, swap the values of pNext and pPrev. Finally, set pHead to the last node in the list.
Node * pCurrent = pHead, *pTemp;
while (pCurrent)
{
pTemp = pCurrent->pNext;
pCurrent->pNext = pCurrent->pPrev;
pCurrent->pPrev = temp;

pHead = pCurrent;

pCurrent = temp;
}
________________________________________
Question: Assume you have an array that contains a number of strings (perhaps char * a[100]). Each string is a word from the dictionary. Your task, described in high-level terms, is to devise a way to determine and display all of the anagrams within the array (two words are anagrams if they contain the same characters; for example, tales and slate are anagrams.)
Answer: Begin by sorting each element in the array in alphabetical order. So, if one element of your array was slate, it would be rearranged to form aelst (use some mechanism to know that the particular instance of aelst maps to slate). At this point, you slate and tales would be identical: aelst.
Next, sort the entire array of these modified dictionary words. Now, all of the anagrams are grouped together. Finally, step through the array and display duplicate terms, mapping the sorted letters (aelst) back to the word (slate or tales).
________________________________________
Question: Given the following prototype:
int compact(int * p, int size);
write a function that will take a sorted array, possibly with duplicates, and compact the array, returning the new length of the array. That is, if p points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 5 returned.
Answer: A single loop will accomplish this.
int compact(int * p, int size)
{
int current, insert = 1;
for (current=1; current < size; current++)
if (p[current] != p[insert-1])
{
p[insert] = p[current];
current++;
insert++;
} else
current++;
}
Happy Programming!


RE: write a c program to reverse the string without us...
________________________________________
#include
#include
main()
{
char str[50],revstr[50];
int i=0,j=0;
printf("Enter the string to be reversed : ");
scanf("%s",str);
for(i=strlen(str)-1;i>=0;i--)
{
revstr[j]=str[i];
j++;
}
revstr[j]='\0';
printf("Input String : %s",str);
printf("\nOutput String : %s",revstr);
getch();
}

write a c program to find whether a stack is
progressing in forward or reverse direction.

#include

void show_stack_dir(int * p) {
printf("%s\n", p < (int*)(&p) ? "up" : "down");
}

int main(int argc, char ** argv) {
show_stack_dir(&argc);
return 0;
}

Given a number, how can u determine using C, whether it is divisible by 3, without using *, /, % operators.

You may assume that itoa() function is available.
convert the number to the string using itoa();

add up all the digits
checkDivisibility(int num){
char *str=itoa(num)

while (1)
{
for (i =0 ; i < strlen(str);i++)
sum= sum + (str[i] - "0");

if (sum > 10)
str=itoa(sum);
else
break;
}

if(sum == 3 || sum == 6 || sum == 9)
printf("Number divisible by 3");
else
printf("Number not divisible by 3");

}


Re: Hexadecimal Conversion
« Reply #6 on: Jul 26th, 2007, 1:02am » Quote Modify

________________________________________
We can change this to...


if( ch >= '0' && ch <='9')
index=ch-'0';
else if(ch >= 'A' && ch <= 'F')
index=10+ch-'A';
else if(ch >='a' && ch <= 'f')
index=10+ch-'a';

Re: Find the Repeated Number
« Reply #5 on: Aug 1st, 2007, 3:20am » Quote Modify

________________________________________

Try and debug thru this code with an appropriate example

int findRepeated(int *arr,int length)
{
int counter=0;
int current=arr[0];
for(i=0;i{
if(counter==0)
{
counter++;
current=arr [ i ];
}
if(counter > 0)
{
if(current == arr [ i ])
{
counter++;
else
counter--;
}
}

return current;

}

Function for finding greatest of three numbers:
int maxof3(int a, int b, int c)
{
return (a + b + c * 2 + abs(a - b) + abs(a + b - c * 2 + abs(a - b))) / 4;
}
Function for finding greatest of four numbers:
int maxof4(int a, int b, int c, int d)
{
return (a + b + c + d + abs (b - a) + abs(d - c) + abs(a + b - c - d + abs( b - a) - abs(d - c)))/ 4;
}