1.Suppose that you have a reference to a specific node (somewhere in the middle)
ID: 663829 • Letter: 1
Question
1.Suppose that you have a reference to a specific node (somewhere in the middle) in a simply linked list (only with forward links) that is guaranteed not to be the last node in the chain. You do not have any reference to any other nodes (except following links from the node for which you have the reference). Suppose the linked list stores integers. Write an O(1) method that logically removes the value stored in that node (for which you have the reference) from the linked list.
2.Write a method for concatenating two singly linked lists L1 and L2 having references to head, into a single list L that contains all the nodes of L1 followed by all the nodes of L2. What is the runtime complexity of the method?
3.Write a method to determine whether a specific node, for which a reference is already supplied, in a doubly linked list is closer to head or tail node. You may need link hopping, but you cannot visit any node twice while traversing the list by link hopping.
4.Write a method for finding, by link hopping, the middle node of a doubly linked list with a reference to head and tail node. You should use link hopping only and cannot use any ‘counter’ to solve this problem.
Explanation / Answer
This question has lot of sub parts. Can you please post one more question.
1.
#include <stdio.h>
#include <stdlib.h>
/* structure of a linked list node */
struct node
{
int data;
struct node *next;
};
void deleteNode(struct node *head, struct node *n)
{
// When node to be deleted is head node
if(head == n)
{
if(head->next == NULL)
{
printf("There is only one node. The list can't be made empty ");
return;
}
/* Copy the data of next node to head */
head->data = head->next->data;
// store address of next node
n = head->next;
// Remove the link of next node
head->next = head->next->next;
// free memory
free(n);
return;
}
// When not first node, follow the normal deletion process
// find the previous node
struct node *prev = head;
while(prev->next != NULL && prev->next != n)
prev = prev->next;
// Check if node really exists in Linked List
if(prev->next == NULL)
{
printf(" Given node is not present in Linked List");
return;
}
// Remove node from Linked List
prev->next = prev->next->next;
// Free memory
free(n);
return;
}
/* Utility function to insert a node at the begining */
void push(struct node **head_ref, int new_data)
{
struct node *new_node =
(struct node *)malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to print a linked list */
void printList(struct node *head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->next;
}
printf(" ");
}
/* Driver program to test above functions */
int main()
{
struct node *head = NULL;
/* Create following linked list
12->15->10->11->5->6->2->3 */
push(&head,3);
push(&head,2);
push(&head,6);
push(&head,5);
push(&head,11);
push(&head,10);
push(&head,15);
push(&head,12);
printf("Given Linked List: ");
printList(head);
/* Let us delete the node with value 10 */
printf(" Deleting node %d: ", head->next->next->data);
deleteNode(head, head->next->next);
printf(" Modified Linked List: ");
printList(head);
/* Let us delete the the first node */
printf(" Deleting first node ");
deleteNode(head, head);
printf(" Modified Linked List: ");
printList(head);
getchar();
return 0;
}
2.
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
/* Pick either a or b, and recur */
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
merge using recursion O(M+N)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.