Detect merged linked list

Given the pointers to 2 linked list, how will we find out if they are merged? i.e. at some point they point to the same address.

Ans

Pick one of the lists and traverse it from head to tail. For each node encountered, compare it to the head pointer of the other list. If you find a match then the second list is embedded within the first list.

If you don't find a match, then repeat the procedure by traversing the second list.

Linked list

How does one find a loop in a singly linked list in O(n) time using constant memory? you cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n)

Ans

One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there's a loop.

Write functions Insert and Remove which add and remove nodes from ordered single linked list based on the Node value

Q:

Write functions Insert and Remove which add and remove nodes from ordered single linked list based on the Node value

A:

public Node Insert(Node head, int value)
{
if (head == null || value < head.value)
return new Node(value, head);
else
{
head.next = Insert(head.next, value);
return head;
}
}

Write a function which will test whether or not there is a cycle in a single linked list

Q:

Write a function which will test whether or not there is a cycle in a single linked list

A:

public bool hasLoop(Node head)
{
Node first = head;
Node second = head;
while (first && second &&
first.Next && second.Next &&
second.Next.Next)
{
first = first.Next;
second = second.Next.Next;
if (first == second)
{
// Found loop
return true;
}
}
return false;
}

Write a function which will print values from the single linked list in the reverse order in O(n) time. No changes to the list can be made and no additional data structures can be used

Q:

Write a function which will print values from the single linked list in the reverse order in O(n) time. No changes to the list can be made and no additional data structures can be used”

A:

public void PrintInReverseOrder (Node head)
{
if (head != null)
{
PrintInReverseOrder(head.next);
Console.WriteLine(head.value);
};
}

Compute the sum of all the values in the nodes of a single linked list

Q:

Compute the sum of all the values in the nodes of a single linked list


A:

public int getSum(Node head)
{


if (head == null) return 0;
else
return getSum(head.next) + head.value;

}

Calculate length of the linked list

Q:

Calculate length of the linked list

A:

public int getLength(Node head)
{
if (head == null)
return 0;
else
return length(head.next) + 1;

}

Reverse a Singly Linked List

Q:
Reverse a Singly Linked List

A:
public Node Reverse(Node head)
{
Node next;
Node current;
current = head;
Node Result = null;
while (current != null)
{
next = current.next;
current.next = result;
result = current;
current = next;
}
return (result);
}

What are the advantages and disadvantages of linked list structure vs. arrays?

Q:

What are the advantages and disadvantages of linked list structure vs. arrays?

A:

Linked lists allow only sequential access to elements O(n) while arrays allow random access O(1). Linked lists requires an extra storage for references, which often makes them impractical for lists of small data items such as characters or Boolean values. From the over side, size of array is restricted to declaration. Insertion/Deletion of values in arrays are very expensive comparing to linked list and requires memory reallocation. Elements can be inserted into linked lists indefinitely, while an array will eventually.

What is the difference between array and linked list?

Q:
What is the difference between array and linked list?

A:

The main difference between the linked list and the array is that while the array is a static data structure (with fix number of elements), the linked list - dynamic data structure. In terms of complexity, the linked list is usually more efficient as to the space it uses, however, algorithms for linked lists are usually more complicated that those of the array.

Reverse a Linked-List

Q:

Reverse a Linked-list. Write code in C.

A:

Recursive solution:

Node * reverse( Node * ptr , Node * previous)
{
Node * temp;
if(ptr->next == NULL) {
ptr->next = previous;
return ptr;
} else {
temp = reverse(ptr->next, ptr);
ptr->next = previous;
return temp;
}
}
reversedHead = reverse(head, NULL);

Non-recursive solution:

Node * reverse( Node * ptr )
{
Node * temp;
Node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
return previous;
}

Singly Linked List – Delete Node

Q:

You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.

A:

void deleteNode( Node * node )
{
Node * temp = node->next;
node->data = node->next->data;
node->next = temp->next;
free(temp);
}

DeleteList()

Q:

Write a function DeleteList() that takes a list, deallocates all of its memory and sets its
head pointer to NULL (the empty list).

A:

Delete the whole list and set the head pointer to NULL. There is a slight complication
inside the loop, since we need extract the .next pointer before we delete the node, since
after the delete it will be technically unavailable.
void DeleteList(struct node** headRef) {
struct node* current = *headRef; // deref headRef to get the real head
struct node* next;
while (current != NULL) {
next = current->next; // note the next pointer
free(current); // delete the node
current = next; // advance to the next node
}
*headRef = NULL; // Again, deref headRef to affect the real head back
// in the caller.
}

Count()

Q:

Write a Count() function that counts the number of times a given int occurs in a list.

A:
int Count(struct node* head, int searchFor) {
struct node* current = head;
int count = 0;
while (current != NULL) {
if (current->data == searchFor) count++;
current = current->next;
}
return count;
}
Alternately, the iteration may be coded with a for loop instead of a while...
int Count2(struct node* head, int searchFor) {
struct node* current;
int count = 0;
for (current = head; current != NULL; current = current->next) {
if (current->data == searchFor) count++;
}
return count;
}