## 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) {

return;
}
else {
reverseList(child, rootContainer);
}
}
}``````

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.

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

Comment hidden because of low score. Click to expand.
0

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;

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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)
{
this.start=root;
return;
}else{

}
}``````

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) {
return ;
}
reverse (node.getNext());
node.getNext().setNext(node);
node.setNext(null);
}``````

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)
{
return;
}
Reverse(node.next);
(node.next).next = node;
node.next = null;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

{
while(ptr->next != NULL)
{
ptr = ptr->next;
}

}
}``````

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

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

}

Call this with

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

}``````

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.

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

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);
}
}``````

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

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

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

}``````

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

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

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
return; //since this is the base case
}

// If not the end of list, then call the same function with next node
recursiveReverse(currentNode.getNext());

// 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);
}``````

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
return;
}
else{

ListNode<T> nextNode = null;
nextNode = node.getNext();
node.setNext(temp);
temp = node;
node = nextNode;

reverseListRecursive(node,temp);
}
}``````

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){
count--;
current=current->next;
reverse();
}

}

public static void main(String args[]){

reverselist r;
r.reverse();
}

}

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

What if ptr is null?

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;
}``````

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.

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