1
\$\begingroup\$

Here is my code to reverse link list in using recursion:

       Node n = null;

    private void ReverseList(Node temp)
    {
        if (temp == null)
            return;

        ReverseList(temp.nextNode);

        Node newNode = temp;
        newNode.nextNode = null;
        if (n == null)
        {
            n = newNode;
        }
        else
        {

            Node TempNode = n;

            while (TempNode.nextNode != null)
            {
                TempNode = TempNode.nextNode;
            }
            TempNode.nextNode = newNode;
             head=n;
        }

    }

Is this the preferred way of doing this? What modifications can I make to optimize this code?

\$\endgroup\$
  • \$\begingroup\$ This code is a non-working code, you're using head variable not declared anywhere in the sources. \$\endgroup\$ – almaz Feb 19 '15 at 13:21
6
\$\begingroup\$

Do use descriptive name for the variables and parameters, all those n, temp, newNode do not tell anything.

Reversing the list using recursion should not rely on 'external' variables as you do with Node n = null;. Given that linked list after reversal should have the last element at its head, I would suggest to pass it through the recursive chain hierarchy as a return value.

Having a loop while (TempNode.nextNode != null) makes recursion useless, as you walk through the list via loops instead of recursion. Try to come up with the approach where you do not need loops to get the head of the resulting linked list.

\$\endgroup\$
0
\$\begingroup\$

No, this is not a preferred way to reverse a linked list, since recursion in this case would take O(N) space, when it's possible to do the same in-place without recursion, which is a constant space algorithm.

UPDATE: Based on the comment, i have to note that the recursive implemenation with a depth of N is considered a programming error if the total algorithm space exceeds the stack size.

If you use such an implementation, you should be running your code only in a new thread, created in a full trust environment, specifying the maximum stack size. According to the documentation of Thread Constructor (ThreadStart, Int32), the specified stack size is ignored in a limited trust environment, so the default stack size would place a limitation on the algorithm implementation.

\$\endgroup\$
  • \$\begingroup\$ @Vogel612 There is if you use the unsafe keyword \$\endgroup\$ – Ben Aaronson Feb 20 '15 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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