Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
void RecursiveReverse(struct node** root ) {
if (*root == NULL)
return;
struct node* cur;
struct node* rest;
cur = *root;
rest = cur->next;
if (rest == NULL)
return;
RecursiveReverse(&rest);
// put the cur elem on the end of the list
cur->next->next = cur;
cur->next = NULL;
// fix the root poniter
*root = rest;
}
void Reverse(struct node** root) {
struct node* result = NULL;
struct node* cur = *root;
while (cur != NULL) {
struct node* next = cur->next;
cur->next = result;
result = cur;
cur = next;
}
*root = result;
}
// Recursion
Node Reverse(Node current, Node pre)
{
Node next=current.next;
current.next=pre;
if(next==null)
return current;
return Reverse(next,current);
}
// iterative
public void Reverse(Node head)
{
Node NextNodeOfCurrent, Prev,Current;
Current = head;
Prev = null;
while(Current !=null)
{
NextNodeOfCurrent = Current.next;
Current.next=Prev;
Prev = Current;
Current=NextNode;
}
}
Reverse the list and return the new head's pointer:
Node* reverse(Node* pre, Node* p)
{
Node* after = p->next;
p->next = pre;
if(after == NULL) return p;
else return (p, after);
}
Node* reverse(Node* head)
{
if(head == NULL || head->next == NULL) return head;
else return reverse(NULL, head);
}
Recursive:
1) Divide the list in two parts - first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer
void recursiveReverselinkedlist(struct node** head)
{
struct node* first_node;
struct node* rest_nodes;
/* empty list */
if (*head == NULL)
return;
first_node = *head;
rest_nodes = first_node->next;
/* List has only one node */
if (rest_nodes == NULL)
return;
/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest_nodes);
first_node->next->next = first_node;
first_node->next = NULL;
*head = rest_nodes;
}
Time Complexity: O(n)
Space Complexity: O(1)
Iterative solution in java:-
class node{
private int val;
node next;
public node(int val){
this.val=val;
next=null;
}
public int getval(){
return this.val;
}
}
class linklist{
node start;
node last;
public linklist(){
start=null;
last=null;
}
public boolean isempty(){
return start==null;
}
public void insert(int val){
node newnode=new node(val);
if(start==null){
start=newnode;
last=newnode;
}
else{
last.next=newnode;
last=newnode;
}
}
public node listreverse(){
node middle=null;
node tail;
if(isempty()){
System.out.println("list empty");
return this.start;
}
else{
while(start!=null){
tail=middle;
middle=start;
start=start.next;
middle.next=tail;
}
return middle;
}
}
}
public class List_reverse {
public static void main(String[] args) {
// TODO Auto-generated method stub
linklist l=new linklist();
l.insert(10);
l.insert(20);
l.insert(30);
l.insert(40);
node a;
a=l.listreverse();
while(a!=null){
System.out.println(a.getval());
a=a.next;
}
}
}
recursive: time = O(n), space = O(n)
iterative: time = O(n), space = O(1)
Node* recursicve_reverse(Node* node)
{
if (node == NULL) return NULL;
if (node->next == NULL) return node;
Node* head = recursive_reverse(node);
node->next->next = node;
node->next = NULL;
return head;
}
Node* iterative_reverse(Node* node)
{
Node* head = NULL;
while (node != NULL)
{
Node* tmp = node->next;
node->next = head;
head = node;
node = tmp;
}
return head;
}
class node{
int value;
node next=null;
node(int v){
this.value=v;
}
void appendToTail(int n){
node end=new node(n);
node current=this;
while(current.next!=null){
current=current.next;
}
current.next=end;
}
}
public class reverse {
public static void main(String[] args) {
// generate a single list
node head=new node(Integer.parseInt(args[0]));
for(int i=1;i<args.length;i++)
head.appendToTail(Integer.parseInt(args[i]));
head=reverseLinkedList(head);
System.out.println("The result is:");
while(head!=null){
System.out.print(head.value);
head=head.next;
}
}
static node reverseLinkedList(node head){
node newHead=head;
if(head==null||head.next==null)
return head;
else{
newHead = reverseLinkedList(head.next);
head.next.next=head;
head.next=null;
return newHead;
}
}
}
- jie.jeff.li December 20, 2013