How can I rewrite this linked-list manipulation as tail-recursive?

Question

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?

Answer 1

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.

• kevin cline: +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)
• scrwtp: true, once you realize you need to pass it in as well.
• scrwtp: I think that's the main hurdle in getting to a tail recursive solution.
• CaptainCodeman: What language is your code written in? Also, for C++ you don't need 3 parameters, I did it with 2. (See my answer)
• scrwtp: F#. It's also valid OCaml.