All About Knowledge: November 2015

Sunday, 29 November 2015

Detect Cycle in Linked List

Problem Statement

You’re given the pointer to the head node of a linked list. Find whether the list contains any cycle (or loop). A linked list is said to contain cycle if any node is re-visited while traversing the list. The head pointer given may be null meaning that the list is empty.

Input Format
You have to complete the int HasCycle(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console. Number of nodes in a linked list doesn't exceed 100.

Output Format
Check whether the linked list has a cycle and return 1 if there is a cycle. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

1 --> NULL

1 --> 2 --> 3
      ^     |
      |     |
       -----

Sample Output

0
1

Explanation
1. First list has no cycle, hence return 0
2. Second list is shown to have a cycle, hence return 1.

Note
After first solving the problem by yourself, see Floyd's cycle-finding algorithm for an efficient solution which uses O(N) time and O(1) additional memory.

/*
Detect loop in a linked list
List could be empty also
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
int HasCycle(Node* head)
{
// Complete this function
// Do not write the main method
if(head == NULL || head->next == NULL || head->next->next == NULL){
return 0;
}
Node* slow = head;
Node* fast = head->next->next;
while(fast->next->next != NULL && slow->next != NULL){
if(fast == slow){
return 1;
}else{
fast = fast->next->next;
slow = slow->next;
}
}
return 0;
}

Delete duplicate-value nodes from a sorted linked list

Problem Statement

You're given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete as few nodes as possible so that the list does not contain any value more than once. The given head pointer may be null indicating that the list is empty.

For now do not be concerned with the memory deallocation. In common abstract data structure scenarios, deleting an element might also require deallocating the memory occupied by it. For an initial intro to the topic of dynamic memory please consult:http://www.cplusplus.com/doc/tutorial/dynamic/

Input Format
You have to complete the Node* RemoveDuplicates(Node* head) method which takes one argument - the head of the sorted linked list. You should NOT read any input from stdin/console.

Output Format
Delete as few nodes as possible to ensure that no two nodes have the same data. Adjust thenext pointers to ensure that the remaining nodes form a single sorted linked list. Thenreturn the head of the sorted updated linked list. Do NOT print anything to stdout/console.

Sample Input

1 -> 1 -> 3 -> 3 -> 5 -> 6 -> NULL
NULL

Sample Output

1 -> 3 -> 5 -> 6 -> NULL
NULL

Explanation
1. 1 and 3 are repeated, and are deleted.
2. Empty list remains empty.

/*
Remove all duplicate elements from a sorted linked list
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
Node* RemoveDuplicates(Node *head)
{
// This is a "method-only" submission.
// You only need to complete this method.
Node* temp = head;
Node* dummy;
if(head == NULL){
return NULL;
}
while(temp->next != NULL){
if(temp->data == temp->next->data){
dummy = temp->next;
temp->next = temp->next->next;
free(dummy);
}else{
temp = temp->next;
}
}
return head;
}

Get Node Value

Problem Statement

You’re given the pointer to the head node of a linked list and a specific position. Counting backwards from the tail node of the linked list, get the value of the node at the given position. A position of 0 corresponds to the tail, 1 corresponds to the node before the tail and so on.

Input Format
You have to complete the int GetNode(Node* head, int positionFromTail) method which takes two arguments - the head of the linked list and the position of the node from the tail. positionFromTail will be at least 0 and less than the number of nodes in the list. You should NOT read any input from stdin/console.

Constraints
Position will be a valid element in linked list.

Output Format
Find the node at the given position counting backwards from the tail. Then return the datacontained in this node. Do NOT print anything to stdout/console.

Sample Input

1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 0
1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 2

Sample Output

6
3

/*
Get Nth element from the end in a linked list of integers
Number of elements in the list will always be greater than N.
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
int GetNode(Node *head,int positionFromTail)
{
// This is a "method-only" submission.
// You only need to complete this method.
Node* tail = head;
int countNode = 1;
if(head == NULL){
return 0;
}
while(tail->next != NULL){
tail = tail->next;
countNode += 1;
}
tail = head;
int positionFromFront = countNode - positionFromTail;
while(positionFromFront > 1){
tail = tail->next;
positionFromFront--;
}
return tail->data;
}

Reverse a doubly linked list

Problem Statement

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty.

Input Format
You have to complete the Node* Reverse(Node* head) method which takes one argument - the head of the doubly linked list. You should NOT read any input from stdin/console.

Output Format
Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Then return the head node of the reversed list. Do NOT print anything to stdout/console.

Sample Input

NULL
NULL <-- 2 <--> 4 <--> 6 --> NULL

Sample Output

NULL
NULL <-- 6 <--> 4 <--> 2 --> NULL

Explanation
1. Empty list, so nothing to do.
2. 2,4,6 become 6,4,2 o reversing in the given doubly linked list.

Reverse a doubly linked list, input list may also be empty

Node is defined as

struct Node

{

int data;

Node *next;

Node *prev;

}

Node* Reverse(Node* head)

{

// Complete this function

// Do not write the main method.

Node* tail = head;

Node* forward = head;

if(head == NULL){

return NULL;

}

if(head->next == NULL){

return head;

}

while(tail->next != NULL){

tail = tail->next;

}

while(forward != tail && forward->prev != tail){

int temp = forward->data;

forward->data = tail->data;

tail->data = temp;

forward = forward->next;

tail = tail->prev;

}

return head;

}

Merge two sorted linked lists

Problem Statement

You’re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format
You have to complete the Node* MergeLists(Node* headA, Node* headB) method which takes two arguments - the heads of the two sorted linked lists to merge. You should NOT read any input from stdin/console.

Output Format
Change the next pointer of individual nodes so that nodes from both lists are merged into a single list. Then return the head of this merged list. Do NOT print anything to stdout/console.

Sample Input

1 -> 3 -> 5 -> 6 -> NULL
2 -> 4 -> 7 -> NULL

15 -> NULL
12 -> NULL

NULL 
1 -> 2 -> NULL

Sample Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
12 -> 15 -> NULL
1 -> 2 -> NULL

Explanation
1. We merge elements in both list in sorted order and output.

/*
  Merge two sorted lists A and B as one linked list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* MergeLists(Node *headA, Node* headB)
{
  // This is a "method-only" submission. 
  // You only need to complete this method 
    Node* temp1 = headA;
    Node* temp2 = headB;
    Node* temp  = NULL;
    Node* dummy;
    if(headA == NULL){
        return headB;
    }else if(headB == NULL){
        return headA;
    }
    if(temp1->data <= temp2->data){
        temp = temp1;
        temp1 = temp1->next;
    }else{
        temp = temp2;
        temp2 = temp2->next;
    }
    dummy = temp;
    while(temp1 != NULL && temp2 != NULL){
        if(temp1->data <= temp2->data){
            dummy->next = temp1;
            temp1 = temp1->next;
            dummy->next->next = NULL;
        }else{
            dummy->next = temp2;
            temp2 = temp2->next;
            dummy->next->next = NULL;
        }
        dummy = dummy->next;
    }
    if(temp1 == NULL){
        dummy->next = temp2;
    }else{
        dummy->next = temp1;
    }
    return temp;
}

Insert a node at the tail of a linked list

Problem Statement

You’re given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer, insert this node at the tail of the linked list and return the head node. The head pointer given may be null meaning that the initial list is empty.

Input Format
You have to complete the Node* Insert(Node* head, int data) method which takes two arguments - the head of the linked list and the integer to insert. You should NOT read any input from stdin/console.

Output Format
Insert the new node at the tail and just return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

NULL, data = 2
2 --> NULL, data = 3

Sample Output

2 -->NULL
2 --> 3 --> NULL

Explanation
1. We have an empty list and we insert 2.
2. We have 2 in the tail, when 3 is inserted 3 becomes the tail.

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* Insert(Node *head,int data)
{
  // Complete this method
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    Node* temp = head;
    node->next = NULL;
    if(head == NULL){
        head = node;
    }else{
        while(temp->next != NULL){
            temp = temp->next;
        }
        temp->next = node;
    }
    return head;
}