Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This is an interview question I was once asked, and now I ask many of my interviewees. I have yet to see anyone come up with a tail-recursive solution during the interview.

Given a liked list, I'd like to swap every pair of nodes as follows:

input: a-b-c-d-e-f-g

output: b-a-d-c-f-e-g

If there's an odd number of nodes then the last node is tacked on as-is. This should be done in-place. Implement the method: Node* SwapTo(Node* start)

I'm using this Node definition:

class Node {
    public:
        char data;
        Node* next;
};

Here's the unoptimized recursive solution:

Node* SwapTwo(Node* start) {
    if (!start) {
        return start;
    }

    Node* second = start->next;
    if (!second) {
        return start;
    }

    Node* third = second->next;
    second->next = start;
    start->next = SwapTwo(third);
    return second;
}

What is the tail-recursive solution?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Since you tagged the question with language-agnostic, here's a solution in a language suited to recursive functions and data structures:

let rec swapTwo lst acc =
    match lst with
    | a::b::tail -> swapTwo tail (a::b::acc)
    | h::tail -> swapTwo tail (h::acc)
    | [] -> List.rev acc 

As for a solution in C++, I don't fancy doing the pointer twiddling details, but I'd start with a function with the following signature:

Node* SwapTwo (Node* start, Node *prev, Node *curr)

Where start would be the head of the list and curr would be what start is in your snippet - the first of the two elements to swap. Then you also need prev, the last node of the previous 'block' to set the next pointer on it.

Probably the prev bit is the most tricky, since you have to update the previous block when you're already processing the next one. The key part to remember when making stuff tail-recursive is that you don't have the stack to utilize in building your computation, you have to pass everything around explicitly to the next recursive call. In your case, that part is where you assign SwapTwo result to start->next.

This should more or less cover it. I don't think I have to comment much on which of those two solutions I find preferable.

share|improve this answer
1  
+1: Not so tricky to handle prev. Start with prev->curr->c2->c3, swap pointers to get prev->c2->curr->c3, then return Swap2(head, curr, c3) –  kevin cline Jun 25 at 10:02
    
true, once you realize you need to pass it in as well. –  scrwtp Jun 25 at 10:12
    
I think that's the main hurdle in getting to a tail recursive solution. –  scrwtp Jun 25 at 10:29
    
What language is your code written in? Also, for C++ you don't need 3 parameters, I did it with 2. (See my answer) –  CaptainCodeman Jun 25 at 13:24
    
F#. It's also valid OCaml. –  scrwtp Jun 25 at 14:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.