3

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?

Improve this question

1 Answer 1

Reset to default
5

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.

Improve this answer
8
  • 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) Commented Jun 25, 2014 at 10:02
  • true, once you realize you need to pass it in as well. Commented Jun 25, 2014 at 10:12
  • I think that's the main hurdle in getting to a tail recursive solution. Commented Jun 25, 2014 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) Commented Jun 25, 2014 at 13:24
  • F#. It's also valid OCaml. Commented Jun 25, 2014 at 14:01

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.