int ReverseString(char *);
main()
{
char *Str;
printf(“enter any stringn”);
gets(Str);
ReverseString(Str);
getch();
}
int ReverseString(char *rev)
{
if(*rev!=’ ’)
{
ReverseString(rev + 1);
putchar(*rev);
}
return 1;
}
non recursion
void ReverseString( char* str, int len )
{
while( len > 1 )
{
swap( &str[0], &str[len – 1] );
++str;
len -= 2;
}
}
Where swap is defined as:
void swap( char* a, char* b )
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
reverse linked list
#include <stdio.h>
// The list element type and head.
struct node {
int data;
struct node *link;
};
static struct node *first = NULL;
// A reverse function which uses only two extra pointers.
void reverse() {
struct node *nxtNode, *curNode;
// curNode traverses the list, first is reset to empty list.
curNode = first;
first = NULL;
// Until no more in list, insert current before first and advance.
while (curNode != NULL) {
// Need to save next node since we’re changing the current.
nxtNode = curNode->link;
// Insert at start of new list.
curNode->link = first;
first = curNode;
// Advance to next.
curNode = nxtNode;
}
}
// Code to dump the current list.
static void dumpNodes() {
struct node *curNode = first;
printf (“==========n”);
while (curNode != NULL) {
printf (“%dn”, curNode->data);
curNode = curNode->link;
}
}
// Test harness main program.
int main (void) {
int i;
struct node *newnode;
// Create list (using actually the same insert-before-first
// that is used in reverse function.
for (i = 0; i < 5; i++) {
newnode = malloc (sizeof (struct node));
newnode->data = i;
newnode->link = first;
first = newnode;
}
// Dump list, reverse it, then dump again.
dumpNodes();
reverse();
dumpNodes();
printf (“==========n”);
return 0;
}
struct node
{
int data;
struct node *link;
};
void reverse()
{
struct node *p = first,
*q = NULL,
*r;
while (p != NULL)
{
r = q;
q = p;
p = p->link;
q->link = r;
}
q = first;
}
//interview questions
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.
struct Node
{
…
bool bVisited;
};
Then, to determine whether a node has a loop, you could first set this flag to false for all of the nodes:
// Detect cycle
// Note: pHead points to the head of the list (assume already exists)
Node *pCurrent = pHead;
while (pCurrent)
{
pCurrent->bVisited = false;
pCurrent = pCurrent->pNext;
}
Then, to determine whether or not a cycle existed, loop through each node. After visiting a node, set bVisited to true. When you first visit a node, check to see if the node has already been visited (i.e., test bVisited == true). If it has, you’ve hit the start of the cycle!
bool bCycle = false;
pCurrent = pHead;
while (pCurrent && !pCycle)
{
if (pCurrent->bVisited == true)
// cycle!
pCycle = true;
else
{
pCurrent->bVisited = true;
pCurrent = pCurrent->pNext;
}
}
A much better approach was submitted by 4Guys visitor George R., a Microsoft interviewer/employee. He recommended using the following technique, which is in time O(N) and space O(1).
Use two pointers.
// 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.
Thanks George!
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++;
}
