In a linked list find the nth node from the end of the list

In a linked list find the nth node from the end of the list
list* foo(list* head, int n)
{
if(!head) return NULL;
list* p1=head;
list* p2=head;
int c=0;
while(p1->next)
{
p1=p1->next;
c++;
if(c>n)
return p2=p2->next;
}
if(c>n)
return p2;
else rturn NULL;
}

detect a cycle in linked list

detect a cycle in linked list
bool foo(list* head)
{
if(!head||!head->next) retrun false;
list* p1=head;
list* p2=head->next;
while(p1!=p2)
{
p1=p1->next;
if(p2->next)
p2=p2->next;
else
return false;

if(p1==p2) return true;

if(p2->next)
p2=p2->next;
else
return false;
}
return true;
}

Create a Circular Link List from a Given Binary Tree.

Create a Circular Link List from a Given Binary Tree.

struct node
{
 struct node* left;
 struct node* right;
 int data; 
}
typedef struct node* Node;

Node* B2L(node* root)
{
 if(!root) return NULL;
  
 Node* listA=B2L(root->left);
 Node* listB=B2L(root->right);
 return append(listA,root,listB);
}

Node* append(Node* listA, Node* root, Node* listB)
{
 if(listA)
  {
   root->next=listA;
   root->prev=listA->prev;
   listA->prev=root;
   root=listA;
  }

 if(listB)
  {
   Node* tail=listB->prev;
   root->prev->next=listB;//tail
   listB->prev->next=root;//tail
   listB->prev=root->prev;//head
   root->prev=tail;
  }
return root;
}

Convert a doubly linked list to a binary search tree in place. Think… Suppose the input list is 3 2 1 6 4 7 This is the way to convert sorted linked l

Convert a doubly linked list to a binary search tree in place. Think…
Suppose the input list is 3 2 1 6 4 7
list* foo(list* head)
{
if(!head) return NULL;
list* head1=head2=NULL;
findNewHead(head,head1,head2);
head->left=foo(head1);
head->right=foo(head2);
return head;
}

findNewHead(list* head, list*& head1, list*& head2)
{
if(!head->next) return;
if(head->val>head->next->val)
head1=head->next;
while(head->next)
{
if(head->val>head->next->val)
head=head->next;
else
{
head2=head->next;
head ->next=NULL;
head2->prev=NULL;
return;
}
}
return;
}

A linked list where a node has two pointers，one point to next node，the other point to an random node. O(n) time，O(1) space to copy this linked list.

A linked list where a node has two pointers，one point to next node，the other point to an random node. O(n) time，O(1) space to copy this linked list.
Suppose original list is x1->x2->x3->x4…->xn
Add new nodes to original list like:
y1->x1->y2->x2->y3->x3->…->yn->xn
yi->rand=xi->rand->next// this should be yi->rand=xi->rand->prev,
So the linked list should be double linked list

reverse linked list

Reverse a linked List using recursion, by using one argument only
list * rev(list *head)
{
if(head==NULL)
return NULL;
if(head->next==NULL)
return head;

list *tail=rev(head->next);
head->next->next=head;
head->next=NULL;
return tail;
}
Node* rev(node* head)
{
Node* curr=head, *pr=null, *next;
While(curr)
{
Next=curr->next;
Curr->next=pr;
Pr=curr;
Curr=next;
}
Return pr;
}

Compare Linked List versus ArrayList.

Compare Linked List versus ArrayList.

Arraylist is a resizable array, Link list does not allow random access. Where as arraylist allows random access. In arraylist the elements are always stored in contiguous memory which is not required in Link List.

design a parking lot, how to implement valet parking use hash table and two linked list, one is parking list, the other is empty list. For each node i

design a parking lot, how to implement valet parking

use hash table to mapping ticket no. and car parking position

How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to

How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to access an individual element in O(1) time?

Use a hash table the key is idx, the value is the current node’s value and next node’s hashed key, so we can random access the individual element also run through the list from item to item.

Given two linked lists, which merge at some point, find the point at which they merge

Given two linked lists, which merge at some point, find the point at which they merge

Use hash table to record all node addresses of list 1, traverse list 2 to look up the first common node on the hash table
Or
Get the length of first list and length of second list, get the difference k between two length, forward the pointer of longer list to the kth node. Compare two pointers, if same, this is the merge point, else forward to the next node, until reach the last node.

list* foo(list* head1, list* head2)
{
if(!head1||!head2) return NULL;
int h1=h2=0;
list* p1=head1;
list* p2=head2;
while(p1)
{p1=p1->next;h1++;}
while(p2)
{p2=p2->next;h2++;}
p1=head1;p2=head2;
while(h1>h2)
{p1=p1->next;h1--;}
while(h2>h1)
{p2=p2->next;h2--;}
while(p1!=p2)
{p1=p1->next;p2=p2->next;}
return p1;
}

Given the head pointer of a link list, how do you detect a cycle in the

Given the head pointer of a link list, how do you detect a cycle in the
link list efficiently?

using to pointer p and q.
p forwards one element each step.
q forwards two elements each step.
If p equal to q in any step, then there is a cycle.

There is a circular track.There are n gas stations of capacity ci. To go from one station to the next station it takes certain amount of gas gi.

There is a circular track.There are n gas stations of capacity ci. To go from one station to the next station it takes certain amount of gas gi.
For any station the gas available may not be enough to get to the next station.
Write a linear time algorithm to find the correct station in which we must start in order to complete one round around the track.

Take a linked list where each node ni is ci-gi. Two node’s pointers p1 and p2, int sum is 0
Choose a start point randomly, which pointed by p1 and p2.
Calculate sum=sum+ni, if the sum is positive, forward p1 by 1, ni=p1->val; else backward p2, ni=p2->val;
Repeat above until p1 and p2 encounter. If sum is positive, there is a path to go through the list.
nice solution!!!