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

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 3

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 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

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;

Answer 6

Objective-C Link class with reverse method:

Link.h

#import <Foundation/Foundation.h>

@interface Link : NSObject

@property(nonatomic) int value;
@property(nonatomic) Link *next;

- (Link*)reversedList;

@end

Link.m

#import "Link.h"

@implementation Link

- (Link*)reversedList {

    Link* head;

    Link *link = self;
    while (link) {

        // save reference to next link
        Link *next = link.next;

        // "insert" link at the head of the list
        link.next = head;
        head = link;

        // continue processing the rest of the list
        link = next;
    }

    return head;
}

@end