Can Recursion Reverse a Singly Linked List in Descending Order?

[evinda]

Hello! (Wave)

I have to write a recursive algorithm, that, given a list in descending order with $M$ elements, creates a new list, that contains the element of the list in ascending order. The list is singly linked and we are given a pointer that shows to the first element of the list.

That's what I have tried:

Node *Ch(Node *L1){ 
      if (L1.next!= NULL) 
          Ch(L1.next) 
      // Create a new node with value L1.data and the next field is NULL
      // then we add this node to the List L2
      return L2; 
}

Could you tell me if it is right? (Thinking)

 

[I like Serena]

Hello! (Wave)

I have to write a recursive algorithm, that, given a list in descending order with $M$ elements, creates a new list, that contains the element of the list in ascending order. The list is singly linked and we are given a pointer that shows to the first element of the list.

That's what I have tried:

Node *Ch(Node *L1){ 
      if (L1.next!= NULL) 
          Ch(L1.next) 
      // Create a new node with value L1.data and the next field is NULL
      // then we add this node to the List L2
      return L2; 
}

Could you tell me if it is right? (Thinking)

Hi! (Smile)

Suppose we apply this to:
$$\boxed{3}\to\boxed{2}\to\boxed{1}\to \text{NULL}$$

What will we get? (Wondering)

 

[evinda]

Hi! (Smile)

Suppose we apply this to:
$$\boxed{3}\to\boxed{2}\to\boxed{1}\to \text{NULL}$$

What will we get? (Wondering)

Don't we get this? (Thinking)

$$\boxed{1}\to\boxed{2}\to\boxed{3}\to \text{NULL}$$

 

[I like Serena]

Don't we get this? (Thinking)

$$\boxed{1}\to\boxed{2}\to\boxed{3}\to \text{NULL}$$

First you go down 3 recursion levels.

Then you add $1$ to L2, so we get: $L2\to \boxed{1} \to \text{NULL}$.

Then we back up a recursion level and add $2$ to L2 to get: $L2\to \boxed{2} \to \boxed{1} \to \text{NULL}$.

And finally add $3$: $L2\to \boxed{3} \to \boxed{2} \to \boxed{1} \to \text{NULL}$.

Or isn't that what you had in mind? (Wondering)

 

[evinda]

First you go down 3 recursion levels.

Then you add $1$ to L2, so we get: $L2\to \boxed{1} \to \text{NULL}$.

Then we back up a recursion level and add $2$ to L2 to get: $L2\to \boxed{2} \to \boxed{1} \to \text{NULL}$.

And finally add $3$: $L2\to \boxed{3} \to \boxed{2} \to \boxed{1} \to \text{NULL}$.

Or isn't that what you had in mind? (Wondering)

With these:
// Create a new node with value L1.data and the next field is NULL
// then we add this node to the List L2

I mean that at L2, we would have a pointer R that points to the last element and at R.next we would put the new element.

Is it wrong? (Thinking)

 

[I like Serena]

With these:
// Create a new node with value L1.data and the next field is NULL
// then we add this node to the List L2

I mean that at L2, we would have a pointer R that points to the last element and at R.next we would put the new element.

Is it wrong? (Thinking)

Then it's okay.
But I guess you should write it out more explicitly. (Nerd)

And alternatively you could add elements to L2 while going down.
Then you can add them to the head of L2 and there is no need to keep track of a tail.

 

[evinda]

Then it's okay.
But I guess you should write it out more explicitly. (Nerd)

A ok! (Nod)

And alternatively you could add elements to L2 while going down.
Then you can add them to the head of L2 and there is no need to keep track of a tail.

How could we do it like that? (Thinking)

 

[evinda]

Also how can we find the complexity of the algorithm? (Thinking)

Is it $T(n)=T(n-1)+c$? Or is there a difference, now that we have pointers? (Worried)

 

[I like Serena]

How could we do it like that? (Thinking)

For instance like:

Node *Ch(Node *L1){ 
      if (L1!= NULL)
          next = L1.next
          Move the node to which L1 points to the head of L2
          Ch(next) 
      return L2; 
}

(Thinking)

Also how can we find the complexity of the algorithm? (Thinking)

Is it $T(n)=T(n-1)+c$? Or is there a difference, now that we have pointers? (Worried)

Yes it is.
The pointers do not make a difference. (Nod)