Thread: compare backward ll ints

If you want to compare the values in reverse order it is better to use double linked list instead of
single linked list.
In double linked list we can have previous and next pointers.So using previous pointer we can take the values in the node in reverse order.

Either use a doubly-linked list or rewrite compare() as a recursive function to traverse the call stack backwards.

Your algorithm is correct.The best way to do that is following.


- Create a doubly linked list.

- Store the integers in the doubly linked list

- Call the compare function with passing two values

- If the first node value itself less than or greater than the second,then simply returns the value according to your information such as -1,if the first one is less than the second,1 if second is greater than the first and 0 if both are equal.

- If the first node value of both numbers are equal,then pass the next node value to compare function recursively until all the digits are compared.

- compare function is called recursively when both the values aren't equal.

Originally Posted by vivekraj

- Create a doubly linked list.

- Store the integers in the doubly linked list

- Call the compare function with passing two values

- If the first node value itself less than or greater than the second,then simply returns the value according to your information such as -1,if the first one is less than the second,1 if second is greater than the first and 0 if both are equal.

- If the first node value of both numbers are equal,then pass the next node value to compare function recursively until all the digits are compared.

- compare function is called recursively when both the values aren't equal.

IBTD, either use a doubly linked list or code compare() recursively.
It's an either-or proposition, they don't complement each other.

There's no need for a doubly-linked list or recursion. You can compare the numbers as they are and store the result of the previous digit in a temporary variable. Although a doubly-linked list might be more efficient I think.

Originally Posted by _Mike

There's no need for a doubly-linked list or recursion. You can compare the numbers as they are and store the result of the previous digit in a temporary variable. Although a doubly-linked list might be more efficient I think.

That's the best approach if it were an open-ended problem; however, the OP is constrained to a singly linked list and only recursion can resolve whether one string of digits is greater/less than or equal to another.

Originally Posted by laserlight

Basically, you can determine which is less than the other by iteration by comparing the length of the singly linked lists. Therefore, the problem lies with linked lists of equal length. However, by keeping track of the current comparison if it is not equal, one can eventually compare linked lists of equal length.

Greater / less than cases aren't a problem; but when same length nos. are nearly equal, say 5496 and 5492. What then?

Yes laserlight is right, what I meant was something like this.

Code:

int compare(const struct integer* l, const struct integer* r)
{
	/* comparison value */
	int comp = 0;

	/* test for NULL pointers */
	if(!l && !r) return 0;
	if(!l) return 1;
	if(!r) return -1;

	while(1)
	{
		/* if both numbers are of equal length,
		 * return the comparison value */
		if(!l && !r) return comp;

		/* test the length of the numbers */
		if(l->next && !r->next) return -1;
		if(!l->next && r->next) return 1;

		/* compare digits */
		if(l->digit < r->digit) comp = 1;
		else if(l->digit > r->digit) comp = -1;

		/* move to next digit */
		l = l->next;
		r = r->next;
	}
}

Return values are:
0 : numbers are equal
-1 : l is the greater number
1 : r is the greater number

I made the assumption that integer is

Code:

struct integer
{
	int digit;
	struct integer* next;
};

And that the numbers don't contain any leading zeroes. Negative numbers are not handled because it's not clear from the OP how they are stored.

Originally Posted by laserlight

Using the algorithm I hinted at, comparing the linked list obtained from 5496 and that obtained from 5492:
1. Initially, result = 0
2. Since 6 > 2, result = 1
3. Since 9 == 9, no change to result
4. Since 4 == 4, no change to result
5. Since 5 == 5, no change to result
6. Both linked lists end at this point, therefore they are of the same length. Thus, final result = 1.

Gotcha! and just in case you were wondering here's my 2c

Code:

int cmprec(sll *p, sll *q)
{
    int rc;

    if (p->next && q->next) rc = cmprec(p->next, q->next);
    else if (p->next && !q->next) return 1;
    else if (!p->next && q->next) return -1;
    else return 0;

    if (!rc) {
        if (p->d > q->d) return 1;
        else if (p->d < q->d) return -1;
        else return 0;
    }
    return rc;
}

Originally Posted by itCbitC

@_Mike:

I tried your program and it works only for digit strings that are equal; and no I didn't use numbers that were negative or had leading zeroes.

Hmm that's weird.
Could you please give me an example of numbers which doesn't work so I can verify if I messed something up?