How to reverse a linearly linked list

The basic idea is to use three pointers and walk them down the list. Within the list, the 'forward' pointer is moved down one item. The 'middle' pointer it left where it is, one behind the 'forward' pointer, while the 'back' pointer is left one behind the 'middle' pointer. The 'next' field of the 'middle' pointer's object is set to point at the 'back' pointer, thus reversing the direction of the link in the middle. At this point, the 'back' pointer is moved up one by assigning it to point at 'middle's object, and middle is moved up one by assigning it to point at 'forward's object, which sets everything up for the next iteration. With that in mind, it's only necessary to take care of the special cases that arise at the beginning and end of the linked list.

Back to the Table Of Questions
View this question

Detecting Palindromes

Array: The trick is writing a routine that does something along the lines of the following:

int  DetectPal( char pch[], int Len )
{
int    i = 0;
int    nUpperBound = Len/2;
while( i < nUpperBound ) 
	{ 
		if( pch[i] !="pch[Len" i++] )
			return FALSE; /*#define FALSE 0 */ 
	} 
	return TRUE /*#define TRUE 0 */ 

Note that this checks only the first half of the list against the second half -- by stopping at Len/2, we don't waste time by checking the second half of the list against the first. Also note that in the case of an odd length array we don't check the middle element against anything, because the integer division will truncate the remainder. Ex: For an array of three elements, we'll check the first against the third, then find that 1 is not less than 1 (3 / 2 = 1.5 => 1) and exit without checking the middle element.

For the string, we do pretty much the same thing, except that we insert a call to strlen, and assign the result to Len. Remember that under C, we can think of pointers and arrays being the same thing. I.E., l and k will be the same at the end of this fragment:

char *p;
char l,k;

l = *(p + 1);
k = p[1];

The variant involving a linearly linked list is somewhat more involved, mainly because you can't back up as easily as you can with an array or string. This can be done recursively, or by iteratively running through the list to the mirror element for each comparison. Recursion will eat up memory (esp. for large lists) and can be slow, while the iterative version will be very slow O(n^2), which can get really bad for large lists.
Does anybody know a quick and efficient way to detect a palindrome in a linked list?

Back to the Table Of Questions
View this question

Display the binary representation of an integer

This shouldnÕt be too tough to code, using the bitwise AND operator, &. The main loop looks something like this:

void BitPattern( long N )
{
	int	iBit = 1 nBitMask = 1;
	while( iBit <= 32 ) /*for 32 bit long integers..*/ 
	{ 
		if( nBitMask & N)
			printf(Ò1Ó); 
		else 
			printf(Ò0); 
		iBit++; 
		nBitMask << /* shifts the bits one bit to the left*/ 
	} 
} 

Back to the Table Of Questions
View this question

Write Quicksort

Quicksort is a popular in-place divide-and-conquer sorting method, because it runs in O(nLg(n) ) on average, and has a relatively low overhead in practice, making it oftentime faster than Mergesort, which is O( nLg(n) ) woest-case. A randomized version of Quicksort can be made to run in O( nLg(n) ) time worst-case.
The basic idea behind quicksort is to pick an element of the array to use as the 'dividing point', or pivot, and the place all smaller elements on one side of the pivot and all larger elements on the other side of the pivot. Quicksort is then called recursively on each of the two subarrays. The pivot can either be choosen randomly or arbitrarily (such as, say, the first element of the current array). One way of rearranging the elements would be to put a pointer at the top of the subarray and another at the bottom of the subarray, and move each toward the other till there is an element under the pointer that is less than ( the 'high' pointer) or greater than (the 'low' pointer) the pivot element. If two elements are found, they're switched. Once the 'low' pointer passes the 'high' pointer, we've set up the subarrays and can call Quicksort on each of them.
There are a couple other ways to solve this problem:

• Get / Remember the algorithm for quicksort
• #include "qsort.h" // I think this might be part of the ANSI standard -- this comes with both Metrowerks C and Microsoft C, at least.

Back to the Table Of Questions
View this question

Swapping Variables w/o additional memory

(given int x,y) :

x=x^y;
y=x^y;
x=x^y;

x = x + y;
y = x - y;
x = x - y;

Unknown Function

This function counts the number of "1" bits in the submitted integer.

Back to the Table Of Questions
View this question

General Questions

Gold Mine

Split the bar into three pieces, of 1 oz., 2 oz., and 4 oz. On the first day, you give the worker 1 oz. of gold. On the second day, you trade the 1 oz. chunk for the 2 oz. chunk. On the third day, you then give him the 1 oz. piece back, and so on and so forth. Essentially it's a swapping question. Another way to think of the question is that once we've divided the bar into 1, 2, and 4 oz. chunks, we give the bar out in combinations corresponding to the binary representation of the number that you're looking for.

Back to the Table Of Questions
View this question

Light Bulb

Turn the first switch on for a while (long enough for the bulb to heat up), then turn the first switch off and turn the second switch on. Leave the switch room and enter the bulb room. The bulb that's on is controlled by the second switch. The hot bulb is controlled by the first switch, and by elimination, the third switch controls the only bulb left

Back to the Table Of Questions
View this question

Four gallons of water

A procedure for getting the four gallons to end up in the five gallon bottle is the following:

1. Fill up the five gallon bottle
2. Fill the three gallon bottle using the water in the five gallon bottle. This leaves you with 2 gallons in the five gallon bottle
3. Dump the water out of the three gallon bottle
4. Pour the 2 gallons fro
5. m the five gal. bottle into the three gal. bottle.
6. Fill up the five gallon bottle
7. Fill up the empty space in the three gallon bottle using the water from the five gallon bottle. Since we have 2 gallons there already (from two steps ago), we pour 1 gallon into the three gal. bottle, filling it up, and leaving four gallons in the five gallon bottle.

Back to the Table Of Questions
View this question

Does the melting ice cube overflow the glass?

No. Water is most dense at 4 degree celcius, which means that when it melts the density will increase, reaching its maximum at 4 degrees Celcius. According to my Chem class, the water molecules in ice are in a hexagonal arrangement with lots of space inbetween. In water's liquid state, the molecules are more disorderly, and the lack of structure allows the molecules to get closer. So, when the ice cube melts, the molecules get closer, the water in the ice cube gets more dense, and the glass doesn't overflow

Back to the Table Of Questions
View this question