Print a simply linked list backwards with no recursion, in two passes at most, using constant extra memory, leaving it intact

Question

You must print a simply linked list backwards:

• Without recursion
• With constant extra memory
• In linear time
• Leaving the list intact
• Added Later Two passes at most

Answer 1

Invert the list, print it forwards, invert again. Each step can be done without violating restrictions except the last one.

EDIT: As cube notes in the comments the second and the third stages can be combined into one pass. This gives two passes – first reverse, then print while reversing again.

Answer 2

You cannot traverse the list backwards without having back pointers available. These can take the form of a second data structure, or mutation of the existing data structure, or even the argument stack (via recursive calls) but the result is that either memory usage will not be constant (it will depend on the length of the list) or the list must be mutated.

There is of course a silly answer that fits your criteria (which means your criteria aren't right) - the algorithm reserves a very large (yet constant) chunk of memory that it can use to store a reversed copy of the list.

(Also if we interpret "leaving the list intact" as meaning that we can mutate it during the operation, the answer is bloody obvious!)

Answer 3

Building on sharptooth's reply, you can combine the printing and second inversion in the same pass.

Edit: The "list is left intact" from a single-threaded view because the post-condition equals the pre-condition.

Edit 2: Not sure how I got the answer, but I'll take it since I've hit the rep cap for the day. I gave sharptooth a +1 too.

Answer 4

You can first check the length of the list. Then create a print-buffer, which you fill in backwards as you traverse the list once again for the information.

Or

You can create another linked list where you add all the printing data in the front when you traverse the first list, and then print the second list from front to back.

Either way makes only two passes at most. The first idea could be done in one pass if you have a header struct that keeps track of the amount of elements in the list.

Edit: I just realised that these ideas does not use constant memory.

The only way to do this sensibly seems to be Sharptooths reply, but that requires three passes.

Answer 5

Here's a C# implementation that holds for all the current rules. It mutates the list during the execution, but the list is restored before returning.

using System;
using System.Diagnostics;

namespace SO1135917.Classes
{
    public class ReverseListPrinter
    {
        public static void Execute(Node firstNode, Action<Node> action)
        {
            Reverse(Reverse(firstNode, null), action);
        }

        private static Node Reverse(Node firstNode, Action<Node> action)
        {
            Node node = firstNode;
            Debug.Assert(node != null);

            Node nextNode = node.Next;
            node.Next = null;
            while (node != null)
            {
                if (action != null)
                    action(node);
                if (nextNode == null)
                    break;
                Node nextNode2 = nextNode.Next;

                nextNode.Next = node;
                node = nextNode;
                nextNode = nextNode2;
            }
            return node;
        }
    }
}

There is one problem, however, and that is that the state of the list is undefined if an exception should occur in the above methods. Probably not impossible to handle though.

A subversion repository of the above code, with unit tests, for Visual Studio 2008 is available here, username and password is both 'guest' without the quotes.

Answer 6

a function like the following might solver your issue:

void invert_print(PtNo l){
  PtNo ptaux = l;
  PtNo last;
  PtNo before;
  while(ptaux != NULL){
    last = ptaux;
    ptaux = ptaux->next;
  }
  while(ptaux != last){
    printf("%s\n", last->info.title);
    ptaux = l;
    before = last;
    while(ptaux != before){
      last = ptaux;
      ptaux = ptaux->next;
    }
  }
}

you will need a structure like the following:

typedef struct InfoNo{
  char title20];
}InfoNo;

typedef struct aPtNo{
  struct InfoNo info;
  struct aPtNo* nextx;
}*PtNo;