Goldman Sachs Interview Question
Country: India
Interview Type: In-Person
reverse( node *Head)
{
if(Head==null)
return;
reverse(Head.next);
System.out.println(Head.data);
}
I do not agree that this solution. It is mentioned not to use any data structure. By using recursion, you are implicitly using stack.
One definiately should tell the interviewer about the above answer but should also mention it is not correct.
The correct solution could be to "reverse the list" and then print in second parse (and re-reverse it again if required)
Start traversing the singly linked list and put the nodes in a stack till you reach the end of the list.
Then pop from the stack.
The elements will be in the reverse order to the original linked list.
Oops.
sorry guys misunderstood the question. It says reverse the linkedlist using same linked list.
void reverse(Node currNode) {
if(currNode != null) {
reverse(currNode.next);
System.out.print(currNode.value + ", ");
}
return;
}
reverse(head);
Well if allowed we can use Collections class in java to sort the LinkedList in reverse order.
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class AV {
public static void main(String[] args) {
List<Integer> ab=new LinkedList<Integer>();
ab.add(1);
ab.add(2);
ab.add(3);
ab.add(4);
Collections.reverse(ab);
for(Integer i: ab){
System.out.print(i);
}
}
}
public void Reverse_linkedlist(Linkedlist ll )
{
int count = 0;
for(int i =1 ; i<ll.getSize(); i++)
{
Node current = ll.getHead();
while(current.getNext().getNext() ! = null)
{
current = current.getNext();
}
count++;
Node temp = current.getNext();
Node current1 = ll.getHead();
for(int j= 1 ; j<count ; j++)
{
current1 = current1.getNext();
}
temp.setNext(current1.getNext());
current1.setNext(temp);
current.setNext(null);
}
}
package sample;
import java.util.LinkedList;
import java.util.List;
public class Linked {
public static void main(String args[]){
List<Integer> l = new LinkedList<Integer>();
l.add(10);
l.add(20);
l.add(30);
l.add(40);
l.add(50);
for(int i = l.size() ; i > 0 ; i--){
System.out.println(l.get(i-1));
}
}
}
public class ReverseLinkedList {
static class Node{
Object value;
Node next;
Node(Object value){
this.value = value;
}
Node next(Node next){
this.next = next;
return next;
}
@Override
public String toString() {
return "Node(" +value +")+>"+(next!=null?next.toString():"|");
}
}
static class SingleLinkedList{
Node head;
void reverse(){
Node cur=head, prev=null;
while(cur!=null){
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
head=prev;
}
}
public static void main(String[] args) {
SingleLinkedList l = new SingleLinkedList();
l.head = new Node(1);
l.head.next(new Node(2)).next(new Node(3)).next(new Node(4)).next(new Node(5));
System.out.println(l.head);
l.reverse();
System.out.println(l.head);
}
}
Output:
Node(1)+>Node(2)+>Node(3)+>Node(4)+>Node(5)+>|
Node(5)+>Node(4)+>Node(3)+>Node(2)+>Node(1)+>|
Reverse the list and display it. Below is code to reverse the linked list using linked list node. No other data structure used. Once you get the linked list, you can print it out.
public LinkedListNode<Integer> reverse(LinkedListNode<Integer> head){
LinkedListNode<Integer> previous = null;
LinkedListNode<Integer> current = head;
LinkedListNode<Integer> next = null;
while(current != null){
next = current.getNext();
current.setNext(previous);
previous = current;
current = next;
}
return previous;
}
struct node
{
int data;
struct node *link;
};
typedef struct node node;
stack<int> output, input;
void reverse(node* root)
{
if(root->link != 0)
reverse(root->link);
output.push(root->data);
}
int main()
{
//take inputs into your stack input
node* r;
//pop elements to put into a linked list
reverse(r)
}
- algos July 13, 2013