CareerCup

public class SinglyLinkedListBackward {






	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedNode root = new LinkedNode("A");
		root.next =  new LinkedNode("B");
		root.next.next = new LinkedNode("C");
		
		//recursiveReverse(root);
		//iterativeReverse(root);
		iterativeReverseWithOutMemory(root);

	}

	
	/**
	 * reverse linked list using iterative approach with O(n2) runtime
	 * reverse the LinkedList and iterate
	 * @param root
	 */
	private static void iterativeReverseWithOutMemory(LinkedNode root) {
		if(root == null) return;
		LinkedNode previousNode = null;
		LinkedNode currentNode = root;
		LinkedNode nextNode = null;
		
		
		while(currentNode.next != null){
			
			nextNode = currentNode.next;
			currentNode.next = previousNode;
			previousNode = currentNode;
			currentNode = nextNode;
			
		}
		currentNode.next = previousNode;
		
		while(currentNode != null){
			System.out.print(currentNode.value+" -> ");
			currentNode = currentNode.next;
		}
	}

	/**
	 * reverse linked list using iterative approach
	 * push node to stack, and pop it
	 * consume O(n) memeory
	 * @param root
	 */
	private static void iterativeReverse(LinkedNode root) {
		if(root == null) return;
		Stack<LinkedNode> stack = new Stack<>();
		
		while(root!=null){
			stack.push(root);
			root = root.next;
		}
		
		while(!stack.isEmpty()){
			System.out.print(stack.pop().value+ "->");
		}
		
	}

	/**
	 * reverse linked list using recursion
	 * @param root
	 */
	private static void recursiveReverse(LinkedNode root) {
		if(root == null) return;
		recursiveReverse(root.next);
		System.out.print(root.value+ "->");
	}
	
	
	
	
	
	
}

class LinkedNode{
	public LinkedNode next;
	public String value;
	public LinkedNode(String value){
		this.value = value;
	}

}

#1) Recursively call on linked list and when recursive operation returns print the current character - recursive also takes O(n) memory as n recursive calls
#2) Iterate over the linked list and add the characters to arraylist and then print them or string reverse after adding them to a string

public class Solution {
  // Question 3
  public void printCharBackward(Node node) {
    if(node == null) {
      return;
    }
    int length = getLinkedListLength(node);
    for(int i = length - 1; i >= 0; i++) {
      int index = 0;
      Node tmp = node;
      while(index != i) {
        tmp = tmp.next;
        index++;
      }
      System.out.printLn(tmp.data);
    }
  }

  private int getLinkedListLength(Node node) {
    int length = 0;
    Node tmp = node;
    while(tmp != null) {
      length++;
      tmp = tmp.next;
    }
    return length;
  }

  ///////////////// Question 4
  public void printCharacterIterative(Node node) {
    Node prev = null;
    Node tmp = node;
    // Reverse the list in (N)
    while(tmp != null) {
      Node next = tmp.next;
      tmp.next = prev;
      prev = tmp;
      tmp = next;
    }
    // Print it O(N)
   tmp = prev;
    while(tmp != null) {
      System.out.printLn(tmp.data);
      tmp = tmp.next;
    }
  }
}

Console.WriteLine("reverLinkedlist");
            LinkedList<string> list = new LinkedList<string>();
            list.AddLast("A");
            list.AddLast("B");
            list.AddLast("C");

            foreach (var item in list)
            {
                Console.WriteLine(item);
            }

            Console.WriteLine("print result");

            foreach(var item in printbackward(list))
            {
                Console.WriteLine(item);
            }
            

            Console.ReadLine();


LinkedList<string> printbackward(LinkedList<string> list1)
            {
                LinkedList<string> list2 = new LinkedList<string>();
                foreach(var item in list1)
                {
                    list2.AddFirst(item);
                }

                return list2;
            }

1. recursion - iterate through list and print after recursion call.
2. Iterative with O(n) memory - put into stack and print poping from the stack.
3. Iterative with O(1) memory and O(n^2) time - for each element starting from the last till the first, iterate to its location and print it.
4. Iterative with O(1) memory and O(n) time with data structure change - iterate over the list and for every element keep the previous one and the next one. Change the current element to point to the previous one instead of the next one (null for the first element). At the end the linked list will be reversed and you can just iterate over it.

For #4 we can reverse the linked list in place:

Node *Reverse(Node *head)
{
	Node *prev = NULL;
	Node *n = head;
	while (n) {
		Node *next = n->next_;
		n->next_ = prev;
		prev = n;
		n = next;
	}
	return prev;
}

Recursive

def recursivly(l):
    if l is None:
        return l
    recursivly(l.next)
    print(l.data)

Iterate

def iterate(l):
    temp = []
    while l is not None:
        temp.append(l.data)
        l = l.next
    while len(temp) >= 1:
        print(temp.pop())

n

def n(head):
    if head is None:
        return head
    current = head
    previous = None
    while current is not None:
        next = current.next
        current.next = previous
        previous = current
        current = next
    return previous

n^2

def n2(head):
    temp = head
    n = 0
    while temp is not None:
        n += 1
        temp = temp.next
    for i in range(0, n):
        x = head
        for k in range(0, n-i-1):
            x = x.next
        print(x.data)