CareerCup

Since space is not a restriction, a simple solution would be to use a stack...

Start from the first node of the linked list and enter every element to the stack as you move on...
Once you reach the end of the LL, just print the stack contents...

Time complexity : O(n)
Space Complexity : O(n)

void printRev(const node* node) {
    if (node) {
        printRev(node->next);
        cout << node->value << endl;
    }
}

What do you mean by linked list is dynamic?

I guess I'm missing something very crucial. I was thinking of using a stack to keep the pointers of the linked list. No recursion, and I'm not manipulating the pointers in the list itself. Can you elaborate on the "dynamic"?

my idea, have an extra pointer and a count.
in first iteration, loop through the end of linked list, and count the number of nodes in linked list.
print the last element.
decrement the count.
then on loop through the linked list count number of times and print the last element.
continue till count is 0.
time complexity O(n^2)

private static void reverse(LinkedList<Integer> lList) {
LinkedList<Integer> temp = new LinkedList<Integer>();
LinkedList<Integer> lList2 = new LinkedList<Integer>();
lList2 = lList;
int len = lList.size();
int t;
for (int i = 0; i < len; i++) {
t = lList2.getLast();
lList2.removeLast();
temp.add(t);
}
System.out.println("Linked List:" + lList2);
System.out.println("reverse Linked List:" + temp);

}

another simple method, hve 3 pointers , back , middle, front

reverse(list *header)
{
middle = header;
front = middle->next;
back = null ;
while(1)
{
// reverse the link for middle node
middle->next = back ;
// reached end of list break
if (front == NULL) break;

// move ahead one node @ a time all the 3 pointers
back = middle;
middle = front;
front = front->next;
}
// middle now points to the last node in the original list.
header = middle ;
}

my soln:

print(list *head)
{
if( head)
print(head->link);
printf("%d",head->data);
return;
}

the first solution is clear enough, avoiding the machine stack depth.

Stack solution however is of order Omega(2N), but doing things iteratively naturally leads to less memory usage (bar stack allocation) due to unstacked function calls.

struct node
{
int a;
struct node*link;
};


struct node*head;


void rev_linklist()
{

struct node* prev_ptr , *temp , *for_ptr;

prev_ptr = head;
temp = for_ptr = head->link;

prev_ptr->link = NULL;

while(for_ptr->link != NULL)
{
temp = for_ptr;
for_ptr = for_ptr -> link;
temp ->link = prev_ptr;
prev_ptr = temp;
}

for_ptr->link = temp;
head = for_ptr;

traverse();

}

note sure abt the question but you could always create a list of objects in one iteration (as space complexity is not an issue), then print the list in reverse.... not sure if we understand the question.

one solution is, find the length of the linked list say n. then traverse the list through n/2, and push into stack from n/2 to n links... Now again start from beginning and swap first link with pop the stack element, and swap second link with pop the next element in stack, continue this till stack is empty

Using a stack is the obvious answer but this is pretty much equals to do-it-yourself-recursive.

Create another double linked list with tail pointer.

using stack can do the reverse of linked list other than recursive or manipulating data/pointers

Maybe I'm missing something, but it's possible to create reversed copy of the list like this:

and

Node = namedtuple("Node", ["value", "next"])

def reverse(n):
cur = None
while n != None:
cur = Node(n.value, cur)
n = n.next
return cur

and

printReversedLinkedList(Node node){

String reversedValue =  new String();
while(node !=null){

reversedValue =node.value+reversedValue;
node=node.next;
}
System.out.println(s);
}

You could also just use StringBuffer if coding in java. Similar to Sidhavratha's solution, but perhaps slightly more simple.

Also O(n) time!

Public void printReverseLinkedList(Node node) {
StringBuffer sb = new StringBuffer();
while (node != null ) {
sb.append(node.value);
node = node.next;

}
System.out.println(sb.reverse().toString());

or

void print_rev(list* head){

     if(head == NULL){
          return;
     }
     else{
          print_rev(head->next);
          cout << head->value << " ";
     }
}

we can take one more list and keep adding elemnts in the front, and then traverse the newly created linked list, and it will contain the objects in reverse order only

public String printReverse(LinkedListNode head)
	{
		int count = 0;
		LinkedListNode current = head;
		if(head == null)
			return null;
		while(current != null)
		{
			count++;
			current = current.next;
		}
		String str = "";
		while(count > 0)
		{
			int currCount = 0;
			current = head;
			while(current != null)
			{
				currCount++;
				if(currCount == count)
				{
					str += current.value;
					count--;
				}
				current = current.next;
			}
		}
		return str;
	}

If the questions says u can use an additional space , then the simplest ans is to store the contents of list in an array. Sort the array ( swap (a[0],a[n-1]), swap(a[1],a[n-2)...and so on). Once the array is sorted , put the value back in list. its O(n) solution.

declare a linked list
Linkedlist<Integer> l1 = new Linkedlist<Integer>();
int lsize;

l1.add("1");
l1.add("2");
l1.add("3");
l1.add("4");

lsize=l1.size();

for (i= lsize;i>=0;i--)
{
System.out.println(" the rev order" +l1.get(i));
}

Just traverse the linked list and reverse the next links and once you get to the end of the list, traverse back and print.

Just traverse the linked list and reverse the next links and once you get to the end of the list, traverse back and print.

I think storing addresses of a list that is dynamic is not good. Its better to clone the data as well. Again if you use a fixed size stack you need to parse the list at least once to get the size, and a dynamic stack is just a list abstracted in a way that it looks like a stack.

#include <iostream>

struct Node
{
    int data;
    Node* next;
    Node():data(0),next(NULL){}
    Node(int x):data(x),next(NULL){}
    Node(Node& that):data(that.data),next(NULL){}
};
std::ostream& operator<<(std::ostream& cout, Node node){
    std::cout << node.data << ": ";
}

struct NodeAddr
{
    Node* addr;
    NodeAddr* next;
    NodeAddr(Node& node):next(NULL){
        addr = &node;
    }
};
std::ostream& operator<<(std::ostream& cout, NodeAddr node){
    if(node.addr)
        cout << *(node.addr);
}

template <class T>
class List
{
public:
    List():mHead(NULL) {}
    List(int count):mHead(NULL) { create(count); }

    ~List()
    {
        while(mHead){
            T* temp = mHead;
            mHead = mHead->next;
            delete temp;
        }
    }

    void prepend(T* node)
    {
        if(mHead == NULL)
            mHead = node;
        else{
            node->next = mHead;
            mHead = node;
        }
    }
    template <typename U>
    void cloneReverseFrom(List<U>& source)
    {
        U* headNode = source.getHeadPtr();
        while(headNode)
        {
            T* node = new T(*headNode);
            prepend(node);
            headNode = headNode->next;
        }
    }

    T* getHeadPtr() {return mHead;}
private:
    void create(int count)
    {
        T* temp = NULL;
        for(int i = 0 ; i < count; i++)
        {
            if(mHead == NULL)
            {
                mHead = new T(i);
                temp = mHead;
            }
            else
            {
                temp->next = new T(i);
                temp = temp->next;
            }
        }
    }
    T* mHead;
};

template <typename T>
std::ostream& operator<<(std::ostream& cout, List<T>& myList)
{
    T* obj = myList.getHeadPtr();
    while(obj){
        cout << *obj;
        obj = obj->next;
    }
    std::cout << std::endl;
}

template <typename T>
void printReverse(List<T>& source)
{
    //Holding Addresses: Not good if input list is dynamic
    List<NodeAddr> list2;
    list2.cloneReverseFrom(source);
    std::cout << list2;

    //Copying Data: works for a dynamic list
    List<Node> list3;
    list3.cloneReverseFrom(source);
    std::cout << list3;
}

int main()
{
    List<Node> list(10);
    std::cout << list;
    printReverse(list);
}

import java.util.ArrayList;

public class PrintLLReverse {
	public static void print(ArrayList<Integer> list) {
		print_helper(list, 0);
	}

	private static void print_helper(ArrayList<Integer> list, int position) {
		if (position >= list.size() - 1) {
			System.out.print(list.get(position) + "\t");
			return;
		}
		print_helper(list, position + 1);
		System.out.print(list.get(position) + "\t");
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(4);
		list.add(5);
		list.add(6);
		list.add(7);
		list.add(6);
		list.add(2);
		list.add(1);
		list.add(9);
		list.add(0);
		print(list);
	}

}