Merging two sorted lists?

Your code is overloaded with if -s inserted for handling "special" cases, which bloats it a lot and makes it difficult to read. This usually happens when you decide to handle special cases "by code" instead of finding a way to handle them "by data". As Andrew Koenig once said, "All problems in Computer Science can be solved by another level of indirection".

That "extra level of indirection" usually works very well with lists, helping to significantly reduce clutter created by those if s.

Your code is overloaded with if-s inserted for handling "special" cases, which bloats it a lot and makes it difficult to read. This usually happens when you decide to handle special cases "by code" instead of finding a way to handle them "by data". As Andrew Koenig once said, "All problems in Computer Science can be solved by another level of indirection".

That "extra level of indirection" usually works very well with lists, helping to significantly reduce clutter created by those ifs. To illustrate the above, here's what my code would look like #define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0) Node* MergeLists(Node* list1, Node* list2) { Node *list = NULL, **pnext = &list; if (list2 == NULL) return list1; while (list1! = NULL) { if (list1->data > list2->data) SWAP_PTRS(list1, list2); *pnext = list1; pnext = &list1->next; list1 = *pnext; } *pnext = list2; return list; } Some might argue that the use of an extra level of indirection in pnext pointer actually makes the code more difficult to read.

I'd agree that for a newbie the approach might pose some difficulties, but for an experienced programmer this should be easily digestible as an idiom.

Thanks. Will consider this kind of approach in attacking problems of this nature in future. That really helped!

– Bragboy Feb 27 '10 at 18:28 2 Wouldn't this attempt to dereference null when null is passed for list2? – meriton Feb 27 '10 at 18:29 @meriton: Yes, it would. I added an extra check :) Thank you.

– AndreyT Feb 27 '10 at 18:30 1 +1 for explanation about indirection and simplifying the while condition to only check the modified pointer. – meriton Feb 27 '10 at 18:35 1 Wouldn't this return NULL if list2 is null but list1 is not empty? – polygenelubricants Feb 27 '10 at 18:36.

The most glaring bug is in your loop, you keep overwriting mergedList->next, losing the previously added node. That is, your returned list will never contain more than two nodes, regardless of input ... It's been a while since I did C, but I would do it as follows: Node* merge(Node* list1, Node* list2) { Node* merged = null; Node** tail = &merged; while (list1 && list2) { if (list1->data data) { *tail = list1; list1 = list1->next; } else { *tail = list2; list2 = list2->next; } tail = &((*tail)->next); } *tail = list1? List1 : list2; return merged; }.

Man! Thats a BIG HOLE!. I really did not notice that.

– Bragboy Feb 27 '10 at 18:12.

My take, with a test case So far all of the answers have been interesting and well done. It's possible that this one is more like what an interviewer would like to see, featuring DRY/DIE, and TDD. :-) #include typedef struct ns { int data; struct ns *next; } Node; Node l1 = { { 1, &l11 }, { 3, &l12 }, { 5, &l13 }, { 7, &l14 }, { 9, &l15 }, {11, 0 }, }; Node l2 = { { 2, &l21 }, { 4, &l22 }, { 6, 0 }, }; Node* MergeLists(Node* list1, Node* list2) { Node *t, **xt; for(xt = &t; list1 || list2;) { Node **z = list1 == NULL?

&list2 : list2 == NULL? &list1 : list1->data data? &list1 : &list2; *xt = *z; xt = &(*z)->next; *z = *xt; } *xt = NULL; return t; } int main(void) { for(Node *t = MergeLists(l1, l2); t; t = t->next) printf("%d\n", t->data); return 0; }.

1 That is an ingenious way of constructing a linked list. Love it. – polygenelubricants Feb 27 '10 at 19:40.

Luca: +1 from me. – tzaman Feb 27 '10 at 18:19 @tzaman: How on world is this a related answer to this question? – Bragboy Feb 27 '10 at 18:33 @Bragaadeesh: Do you have to sort?

I wonder why not use well known algorithms. Surely you get best performances using Divide & Impera pattern, instead of simply iterating over the two lists.It is just a critics about the algorithm pattern, indeed it seems to me pertinent. – Luca Piccioni Feb 27 '10 at 18:45 1 It's about merging two sorted lists.

The second part of merge sort is merging two sorted lists.It's pretty straight forward. – Ross Feb 27 '10 at 19:29 1 I was hasty, I agree now. – Bragboy Feb 27 '10 at 20:03.

Merge2(n1, n2) : merge2(n2, n1); } Assuming that you understand recursion, this is as clear as it gets. I should point out that this is good for an interview answer only (where presumably demonstrating clarity of thought has more impact than simply showing that you know how to write programs). In practice, you wouldn't want to merge this way, since it uses O(n) stack depth, which likely would cause a stack overflow.

Also, it's not a tail-recursion, so it's not compiler-optimizable.

Freakin cool! – Bragboy Feb 27 '10 at 18:27 1 Well, it takes getting used to, but unless you abuse it, nested ternaries actually makes for a very clear code to me at least. It requires good logic and good formatting, some parentheses and some indentation, but that's about it.

– polygenelubricants Feb 27 '10 at 18:31 1 It is "elegant" in a sense that it uses recursion. But from the functional point of view, using recursion in a straightforwardly cyclical situation is not exactly an example of functional elegance. Any cycle can be replaced with recursion.

But should it be? – AndreyT Feb 27 '10 at 18:36 2 If I were you, I would resist the need to create an extra function :) You could've easily done it with one function by using , operator. The last branch would simply look as n1->data data?

N1->next = merge(n1->next, n2), n1 : n2->next = merge(n2->next, n1), n2. But that starts to smell of Obfuscated C Code Contest :) – AndreyT Feb 27 '10 at 18:56 1 Yes, the contrast between your solution and mine is that yours (after all the bugs are fixed) shows that the author knows how to write correct code. Mine shows that the author knows how to think clearly.

– polygenelubricants Feb 27 '10 at 19:02.

N1 : (n1->data data)?(n1->next = merge(n1->next, n2), n1) : (n2->next = merge(n2->next, n1), n2)} I can't claim credit for this one, but it is the most concise and shows the symmetry between the two arguments, doesn't introduce any obscure helper functions. I am not sure an optimizing compiler will see a tail recursion here but I do. The indentation is a final touch.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.