Print a linked list in reverse recursively and non-destructively.

Question

simple · Accepted Answer

package PrintLinkedListRecursively;

public class PrintLinkedListRecursively {

	public static void main(String args[])
	{
		Node head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		head.next.next.next = new Node(4);
		
		printReverse(head);
	}
	
	public static void printReverse(Node head){
		if(head == null)
			return;
		
		printReverse(head.next);
		System.out.print(head.data + " ");
	}
}


class Node
{
	int data;
	Node next;
	
	public Node(int data)
	{
		this.data = data;
	}
}

Sigiloso · Answer

a linked list is the worst case scenario (least balanced case) for a binary search tree; equivalently this problem can be viewed as an inorder traversal of a degenerate BST..
You start at the head of the list
You call the function on the next node (recursively)
When the recursive call returns you print the current node and return
if the next node is NULL youve reached the end of the linked list so you print the node's value and return (base case)

Sigiloso · Answer

How about iteratively push values on a stack and at the end pop everything ?!!

Alex Rashkov · Answer

class PrintReverseList {
    private static boolean printTree = false;

    public void reverse() {
        head = reverseAndPrint(null, head);
    }

    public Node reverseAndPrint(Node reverse, Node current) {
        if (current == null) {
            printTree = true;
            return reverse;
        }

        Node next = current.getNext();
        current.setNext(reverse);
        reverse = current;
        current = next;

        Node reverseReturn = reverseAndPrint(reverse, current);

        if (printTree) {
            System.out.println("Reverse N: " + reverse.getData());
        }

        return reverseReturn;
    }
}

Sigiloso · Answer

public static void printRevReursively(Node head){
		if(head == null)
			return;
		printRevReursively(head.next);
		System.out.print(head.value+" ");
		
	}

rsingh0604 · Answer

Agree that this a Inorder Traversal scenario for the tree, assume the next pointer of a node is the rightChild  and tree does have left child  

		//print data recursively and non destructively ---> its an inorder traversal for BST worst case.
		public static void  PrintRecData(LinkedListNode Node) {
			if(Node == null)
			return;
			if(Node.next!=null)
			PrintRecData(Node.next);	
			System.out.print(" "+ Node.a);

	}

X · Answer

{{{

void printLinkedList(Node n){ 
    
String s = ""; //for optimisation, can be string buffer/string builder
while(n!=null){
s = n.data + "
" +s;
n = n.next;
}  
System.out.println(s);
}
}}}

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas