Lab126 Interview Question
Software Engineer InternsCountry: United States
Interview Type: In-Person
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;
}
}
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;
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..
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...
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);
}
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 - 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?
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;
}
}
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);
}
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);
}
}
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;
}
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);
}
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);
}
}
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();
}
}
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;
}
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.
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.
- famee February 24, 2013