Lab126 Interview Question for Software Engineer Interns


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

We can use an arraylist to store old root of the list and new root of the list.
Before the execution, list will contain only old root, after the execution, list will contain old root and new root.

static void reverseList(Node head, ArrayList<Node> rootContainer) {

    if(head == null) return;
    else if(head.next == null) {
      rootContainer.add(head);
      return;
    }
    else {
      Node child = head.next;
      reverseList(child, rootContainer);
      head.next.next = head;
      if(head == rootContainer.get(0)) {
        head.next = null;
      }
    }
  }

- famee February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If a class List has a linked list ListNodes, then yes, it will work.

- Anonymous February 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 10 vote

works like a charm...
public static void reverse(Node root) {
if(root==null || root.next==null) {
return;
}
else {
reverse(root.next);
root.next.next=root;
root.next=null;
}
}

- Anshul February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I understand that the recursive call will help to get to the last node.
But this i cannot get this:
Could you please explain how this part works?:

root.next.next=root;
root.next=null;

- abhisheknm01 February 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrong , we lose the address of last node (i.e address of root node of newly created list)
So resulting list is not accessible

- rinku goel February 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rinku..
since we are not allowed to return the head pointer of resulting list...caller has to himself take care of the resulting node's head pointer by storing the last node...or we can create a wrapper function calling this one and setting the last node as head in a static variable when we reach the end of recursion in this function...no need to pass it with every recursive call.

@abhishek
when you reach 2nd last node...you want to point last node to 2nd last and 2nd last to 3rd last....
so at 2nd last recursive call root will have 2nd last node....now you are doing root.next.next that means last node's next pointer and you are pointing it to root, that means 2nd last node i.e
1->2->3->4 becomes 1->2->3<-4 in last call then
1->2<-3<-4 and so on...

- Anshul February 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

just one correction in your code:
Supposing start to be the variable containing start node value of the linkedlist

public void reverseLink(Node<T> root)
	{
		if(root.getNextLink()==null){
			this.start=root;
			return;
		}else{
			
		}
		reverseLink(root.getNextLink());
		(root.getNextLink()).setNextLink(root);
		root.setNextLink(null);
	}

- novice.not October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Java

public void reverse(Node node) {
		if(node.getNext() == null || node == null) {
			head = node;
			return ;
		}
		reverse (node.getNext());
		node.getNext().setNext(node);
		node.setNext(null);
	}

- Lovish Mittal May 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Public void Reverse(Node node)
{
	if (node == null) return;
	if (node.next == null)
	{
		head = node;
		return;	
	}
	Reverse(node.next);
	(node.next).next = node;
	node.next = null;
}

- Golnaz May 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Golnaz - could you please explain.
For instance linkedlist has 1-2-3-4 elements in it. Head is given as input i.e.. 1 then

Reverse(2)
Reverse(3)
Reverse(4) ---- here 4.next is null so head = 4
(node.next).next = (4.next).next but is n't 4.next null so how are we setting the value?

- manisha.royyuru June 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Public void Reverse(Node node,int caller)
{
	if (node == null) return;
	if (node.next == null)
	{
		head = node;
		return;	
	}
	Reverse(node.next,0);
	(node.next).next = node;
        if(caller == 1)
	node.next = null;
}

call function with Reverse(head,1);

- saurabh July 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to take the head node out, reverse the rest of the list and add the head node back to the end. Something like -

void reverse(node*& head, node*& newHead)
{
	if(head == NULL) return; //end of list, return
	
	node* next = head->next;
	node* revListHead = NULL;
	reverse(next, revListHead); // we get the head of the reverse list
	
	if(revListHead != NULL)
	{
		node* ptr = revListHead;
		while(ptr->next != NULL)
		{
			ptr = ptr->next;
		}

		ptr->next = head;
		head->next = NULL;
	}	
}

- Anonymous July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void rev(Node node,Node prev) {
		if(node == null) {
			list.headNode = prev;
			return;
		}
		Node temp = node.next;
		node.next = prev;
		rev(temp,node);

}

Call this with
rev(list.headNode,null);

- codewarrior October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverseListRecursive(LinkedList** startPtr, LinkedList *curr,LinkedList *prev, LinkedList *fwd)
{
    if(*startPtr == NULL){
        return;
    }
    if (fwd == NULL){
        curr->next = prev;
        *startPtr = curr;
        return;
    }
    
    curr->next = prev;
    prev = curr;
    curr = fwd;
    fwd = fwd->next;
    reverseListRecursive(startPtr, curr,prev, fwd);
    
}

- new bee March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can use a stack.
start iterating the list and add elements in stack.
later pop the stack.
to insert in stack call list recursivly.

- pinkyrjk March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ReverseLinkedList {
    public static class Node {
        String data;
        Node next;
    }

    public static void reverse(Node node, Node parent){
        if (node == null) {
            return;
        }
        reverse(node.next,node);
        node.next = parent;
    }
    
    public static void printNode(Node head){
        Node n = head;
        while(n != null) {
            System.out.print(n.data + "-->");
            n = n.next;
        }
        System.out.println();
    }

    public static void main(String[] args){
    
        Node a = new Node();
        Node b = new Node();
        Node c = new Node();
        
        a.data="a";
        b.data="b";
        c.data="c";
        
        a.next = b;
        b.next = c;
        
        printNode(a);
        reverse(a,null);
        printNode(c);
    }
}

- Rafael Torres April 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reverseListRecursive(Node<E> headList) {
		if (headList == null)
			return;
		Node<E> firstNode = headList;
		Node<E> restNode;
		restNode = firstNode.next;
		if (restNode == null) {
			head = headList;
			return;
		}

		reverseListRecursive(restNode);
		firstNode.next.next = firstNode;
		firstNode.next = null;

		headList = restNode;
	}

- saurzcode June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node *head;
void reverse(node *node)
{
	if (!node->next) {
		head = node;
		return;
	}
	reverse(node->next);
	struct node *temp = node->next;
	temp->next = node;
	node->next = NULL;
}

- aka August 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Creating your own Linked List class with private head field, this is possible to do so recursively.

public void recursiveReverse(LinkedListNode<T> currentNode){  
		// check if the list is empty 
		if(currentNode == null){
			return;
		}
		
		/* if we have recursed till the last node in the list 
		then we have to set it to head. This is recursive base case. */
		if(currentNode.getNext() == null){ 
			// set list head to current last node (tail) since we are reversing list
			this.head = currentNode; 
			return; //since this is the base case
		}
		
		// If not the end of list, then call the same function with next node
		recursiveReverse(currentNode.getNext());
		
		// add link from next to previous, will create cycle temporary 
		// Ex: 1-->2 will become 1<-->2
		currentNode.getNext().setNext(currentNode);

		// Set the old next pointer to null, since reversing list
		// So now it will become 2-->1 from above example
		currentNode.setNext(null);
	}

- Ketan Mehta September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reverseListRecursive(ListNode<T> node, ListNode<T> temp){ 
		
		if(node == null){			//Checking for empty list
			this.head = temp;
			return;
		}
		else{
			
			ListNode<T> nextNode = null;
			nextNode = node.getNext();
			node.setNext(temp);
			temp = node;
			node = nextNode;
			
			reverseListRecursive(node,temp);
		}
	}

- Ram December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node {

int data;
struct node *data;
};

class revserselist{
struct node s;

public void reverse(){
static int count;
static struct node *current=s;
if(count==0){
for(struct node *temp=s;temp!=null;temp=temp->next,count++);
}
else if (count>1) {

for(struct node *temp=s;temp->next->next!=null;temp=temp->next);
struct node *swap = temp->next;
temp->next=current;
current=swap;
if(swap->next==null){
s=temp; //change of header
count--;
current=current->next;
reverse();
}

}

public static void main(String args[]){

reverselist r;
r.reverse();
}


}

- a.mookambika July 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

it must be this we must pass 2 argument first for the node address next is address of node pointer to update the root node . Initial call must be rev (root,&root);

void rev(node *ptr,node** root)
{
if(ptr->next==NULL)
{
*root=ptr;
return;
}
rev(ptr->next,root);
ptr->next->next=ptr;
ptr->next=NULL;
}

- rinku goel February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yup, nice approach. double pointer make it possible to reassign the root. Such easy reassignment is hard in case of Java because in java we cannot pass references (double pointer in this case). We need an encapsulator object to do such reassignments.

- famee February 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if ptr is null?

- Vipul February 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static void reverse(final Node node, final Node prevNode) {
        if (node.next == null) {
            node.next = prevNode;
        } else {
            reverse(node.next, node);
        }

        node.next = prevNode;
    }

- Jack February 24, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More