Skip to main content
Formatting and a bit more explanation on prev
Source Link
scrwtp
  • 4.5k
  • 1
  • 26
  • 29

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 startstart would be the head of the list and currcurr would be what start is in your snippet - the first of the two elements to swap. Then you also need prevprev, the last node of the previous 'block' to set the next pointer on it. 

Probably the prevprev bit is the most tricky, since you have to update the previous block when you're already processing the next one. I think thisThe 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.

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. I think 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.

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.

Source Link
scrwtp
  • 4.5k
  • 1
  • 26
  • 29

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. I think 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.