Here the list of questions about linked list
typedef struct node
{
struct node* link ;
int data ;
}node ;
static void reverse(node** head)
{
node* cur = *head ;
node* prev = NULL ;
node* next = cur->next ;
while (cur->next != NULL)
{
next = cur->next ;
cur->next = prev ;
prev = cur ;
cur = next ;
}
*head = prev ;
}
// Remove nth node from list
void remove_nth_from_last(node** head, int n)
{
node* cur = head ;
while (n--)
cur = cur->next ;
node* slow = head ;
while (cur->next != NULL)
{
cur = cur->next ;
slow = slow ->next ;
}
// slow now points the node pointing from last nth node
node* temp = slow ;
temp->next = slow ->next ;
temp->data = slow->next->data ;
free(slow) ;
}
node* merge_sorted_list(node* l1, node* l2)
{
node head = (node*) getnode(0) ;
node* tail = &head ;
while (l1->next != NULL && l2->next != NULL)
{
if (l1->val < l2->val)
{
tail ->next = getnode(l1->val) ;
l1 = l1->next ;
}
else
{
tail->next = getnode(l2->val) ;
l2 = l2->next ;
}
tail = tail->next ;
}
if (l1->next)?tail->next = l1 : tail->next = l2 ;
return head->next ;
}
// return
// 0 -- loop not found
// 1 -- loop found
int detect_loop(node* head)
{
if (head == NULL)
return 0 ;
node* slow = head, *fast = head ;
while (fast->link != NULL)
{
if (fast->link == NULL)
return 1 ;
if (slow == fast)
return 1 ;
fast = fast->link ;
if (slow == fast)
return 1 ;
slow = slow->next ;
fast = fast->next ;
}
return 0;
}
typedef struct node
{
struct node* link ;
int data ;
}node ;
static void reverse(node** head)
{
node* cur = *head ;
node* prev = NULL ;
node* next = cur->next ;
while (cur->next != NULL)
{
next = cur->next ;
cur->next = prev ;
prev = cur ;
cur = next ;
}
*head = prev ;
}
// Remove nth node from list
void remove_nth_from_last(node** head, int n)
{
node* cur = head ;
while (n--)
cur = cur->next ;
node* slow = head ;
while (cur->next != NULL)
{
cur = cur->next ;
slow = slow ->next ;
}
// slow now points the node pointing from last nth node
node* temp = slow ;
temp->next = slow ->next ;
temp->data = slow->next->data ;
free(slow) ;
}
node* merge_sorted_list(node* l1, node* l2)
{
node head = (node*) getnode(0) ;
node* tail = &head ;
while (l1->next != NULL && l2->next != NULL)
{
if (l1->val < l2->val)
{
tail ->next = getnode(l1->val) ;
l1 = l1->next ;
}
else
{
tail->next = getnode(l2->val) ;
l2 = l2->next ;
}
tail = tail->next ;
}
if (l1->next)?tail->next = l1 : tail->next = l2 ;
return head->next ;
}
// return
// 0 -- loop not found
// 1 -- loop found
int detect_loop(node* head)
{
if (head == NULL)
return 0 ;
node* slow = head, *fast = head ;
while (fast->link != NULL)
{
if (fast->link == NULL)
return 1 ;
if (slow == fast)
return 1 ;
fast = fast->link ;
if (slow == fast)
return 1 ;
slow = slow->next ;
fast = fast->next ;
}
return 0;
}
No comments:
Post a Comment