8 + Interview Questions in Linked List Interview Questions for Experienced in Linked List Interview Questions Page 1 InterviewSolution

1.	Given a linked list with each node representing a linked list and two pointers of its type given below. You need to flatten the lists into a single linked list. The flattened linked list also needs to be sorted. Discuss the approach.
Answer» Pointer to the next node in the main list (the "right" pointer). Pointer to a linked list, this node being the head (the 'down' pointer). The APPROACH is to use the merge() procedure of merge sort for linked lists. To merge lists one by one, we use merge(). We merge() the current list with the flattened list recursively. The flattened list's nodes are linked via the down pointer. Another approach is to use heaps. It is important to notice that there are N nodes connecting in a downward manner from each top node, but those downward nodes are in sorted ORDER. As a result, the objective is to sort everything in ASCENDING order (or decreasing order). Push all the heads of the linked lists in the priority queue's downward list. Pop the node with the smallest priority from the priority queue. Check the node's location so that the next node which is being pointed by the current node can be inserted into the priority queue. Pop the smallest element once more and push the next node pointed by the current node until the heap is empty. Continue to add node data to a new linked list that is POPPED out to the new list. Print the above-mentioned linked list. struct CMP { bool operator()(Node* x, Node* y) { return x->value > y->value; }};//the following function returns the flattened linked list’s rootNode* flattenList(Node* root){ Node* p = root; Node* head = NULL; // this min heap returns the current smallest element in the heap priority_queue < Node, vector <Node>, cmp > pqueue; // the head nodes of every // downward linked list is pushed into the heap while (p) { pqueue.push(p); p = p->right; } while (!pqueue.empty()) { // pop out the topmost node Node* t = pqueue.top(); pqueue.pop(); if (t->down) { pqueue.push(t->down); } // Create the required linked list if (head != NULL) p->down = t; else head = t; p = t; p->right = NULL; } // Pointer to head node return head;}void printList(Node* head){ while (head != NULL) { cout << head->value << ” “ << endl; head = head->down; }} Time Complexity : O(nlogn) Space Complexity : O(n) Conclusion: We hope that this article has helped you learn the fundamentals and advanced questions of linked lists. These questions cover the most important concepts related to linked lists which will help you in both interview and understanding this data structure in depth.

1.

Given a linked list with each node representing a linked list and two pointers of its type given below. You need to flatten the lists into a single linked list. The flattened linked list also needs to be sorted. Discuss the approach.

Answer»

Pointer to the next node in the main list (the "right" pointer).
Pointer to a linked list, this node being the head (the 'down' pointer).

The APPROACH is to use the merge() procedure of merge sort for linked lists. To merge lists one by one, we use merge(). We merge() the current list with the flattened list recursively.
The flattened list's nodes are linked via the down pointer.

Another approach is to use heaps. It is important to notice that there are N nodes connecting in a downward manner from each top node, but those downward nodes are in sorted ORDER. As a result, the objective is to sort everything in ASCENDING order (or decreasing order).

Push all the heads of the linked lists in the priority queue's downward list.
Pop the node with the smallest priority from the priority queue.
Check the node's location so that the next node which is being pointed by the current node can be inserted into the priority queue.
Pop the smallest element once more and push the next node pointed by the current node until the heap is empty.
Continue to add node data to a new linked list that is POPPED out to the new list.
Print the above-mentioned linked list.

struct CMP { bool operator()(Node* x, Node* y) { return x->value > y->value; }};//the following function returns the flattened linked list’s rootNode* flattenList(Node* root){ Node* p = root; Node* head = NULL; // this min heap returns the current smallest element in the heap priority_queue < Node*, vector <Node*>, cmp > pqueue; // the head nodes of every // downward linked list is pushed into the heap while (p) { pqueue.push(p); p = p->right; } while (!pqueue.empty()) { // pop out the topmost node Node* t = pqueue.top(); pqueue.pop(); if (t->down) { pqueue.push(t->down); } // Create the required linked list if (head != NULL) p->down = t; else head = t; p = t; p->right = NULL; } // Pointer to head node return head;}void printList(Node* head){ while (head != NULL) { cout << head->value << ” “ << endl; head = head->down; }}

Time Complexity : O(nlogn)
Space Complexity : O(n)

Conclusion:

We hope that this article has helped you learn the fundamentals and advanced questions of linked lists. These questions cover the most important concepts related to linked lists which will help you in both interview and understanding this data structure in depth.

Discussion

2.	In a standard Doubly Linked List, two address fields are required to contain the addresses of previous and next nodes. Can you create a doubly linked list using only one space for the address field with every node?
Answer» Yes, there is a memory-saving version of the Doubly Linked List that uses only one space for the address FIELD in each node. Because the list uses the bitwise XOR operation to save space for one address, it is known as the XOR Linked List or Memory Efficient. Instead of storing actual memory addresses, each node in the XOR linked list stores the XOR of previous and NEXT node addresses. In the XOR REPRESENTATION, let's call the address variable npx (XOR of next and previous). We can traverse the XOR Linked List in both forward and reverse DIRECTIONS while traversing it. We must remember the address of the previously visited node when traversing the list in order to DETERMINE the address of the next node. Node W: npx = 0 XOR add(X) Node X: npx = add(W) XOR add(Y) Node Y: npx = add(X) XOR add(Z) Node Z: npx = add(Y) XOR 0 Calculation: npx(Y) XOR add(X) => (add(X) XOR add(Z)) XOR add(X) // npx(Y) = add(X) XOR add(Z) => add(X) XOR add(Z) XOR add(X) // w^x = w^x and (w^x)^y = w^(x^y) => add(Z) XOR 0 // x^x = 0 => add(Z) // x^0 = x

2.

In a standard Doubly Linked List, two address fields are required to contain the addresses of previous and next nodes. Can you create a doubly linked list using only one space for the address field with every node?

Answer»

Yes, there is a memory-saving version of the Doubly Linked List that uses only one space for the address FIELD in each node. Because the list uses the bitwise XOR operation to save space for one address, it is known as the XOR Linked List or Memory Efficient. Instead of storing actual memory addresses, each node in the XOR linked list stores the XOR of previous and NEXT node addresses.

In the XOR REPRESENTATION, let's call the address variable npx (XOR of next and previous).

We can traverse the XOR Linked List in both forward and reverse DIRECTIONS while traversing it. We must remember the address of the previously visited node when traversing the list in order to DETERMINE the address of the next node.

Node W:
npx = 0 XOR add(X)

Node X:
npx = add(W) XOR add(Y)

Node Y:
npx = add(X) XOR add(Z)

Node Z:
npx = add(Y) XOR 0

Calculation:

npx(Y) XOR add(X)
=> (add(X) XOR add(Z)) XOR add(X) // npx(Y) = add(X) XOR add(Z)
=> add(X) XOR add(Z) XOR add(X) // w^x = w^x and (w^x)^y = w^(x^y)
=> add(Z) XOR 0 // x^x = 0
=> add(Z) // x^0 = x

Discussion

3.	Given a singly linked list with an additional "arbitrary" pointer at each node that currently points to NULL. What algorithm will you implement to make the "arbitrary" pointer point to the next node with a greater value?
Answer» A simple SOLUTION is to go through all nodes one by one, finding the node with the next bigger VALUE than the current node and changing the next pointer for each node. This solution has an O time complexity (n^2). An Efficient Solution takes O(nLogn) time to complete. The APPROACH is to use MERGE Sort for linked lists. Traverse input list and for each node, copy the next pointer to arbit pointer. Sort the linked list formed by arbit pointers USING Merge Sort. Here, all of the merge sort methods are altered to work with arbit pointers rather than the next pointers.

3.

Given a singly linked list with an additional "arbitrary" pointer at each node that currently points to NULL. What algorithm will you implement to make the "arbitrary" pointer point to the next node with a greater value?

Answer»

A simple SOLUTION is to go through all nodes one by one, finding the node with the next bigger VALUE than the current node and changing the next pointer for each node. This solution has an O time complexity (n^2).

An Efficient Solution takes O(nLogn) time to complete. The APPROACH is to use MERGE Sort for linked lists.

Traverse input list and for each node, copy the next pointer to arbit pointer.
Sort the linked list formed by arbit pointers USING Merge Sort.

Here, all of the merge sort methods are altered to work with arbit pointers rather than the next pointers.

Discussion

4.	Given a linked list, find the length of the longest palindrome list that appears in that linked list using O(1) extra space.
Answer» The concept is built on reversing a linked list iteratively. We LOOP through the given linked list, reversing each prefix of the linked list one by one from the left. We discover the longest common list beginning with the reversed prefix and the list after the reversed prefix, after reversing a prefix. Time complexity is O(n^2). Implementation: int calcCommon(NODE x, Node y){ int cnt = 0; // count common in the list starting // from node x and y while (1) { // increase the count by one for same VALUES if (x-&GT;value == y->value) cnt++; else break; x = x->next; y = y->next; } return cnt;}// Returns length of the longest palindrome sublistint maxPalindrome(Node head){ Node previous = NULL, current = head; int answer = 0; // loop running till the end of the linked list while (1) { if(current==NULL) break; // reversed sublist from head to current Node next = current->next; current->next = previous; // check for odd length palindrome answer = max(result, 2calcCommon(previous, next)+1); // check for even length palindrome answer = max(result, 2calcCommon(current, next)); // UPDATE previous and current for next iteration previous = current; current = next; } return answer;}

4.

Given a linked list, find the length of the longest palindrome list that appears in that linked list using O(1) extra space.

Answer»

The concept is built on reversing a linked list iteratively. We LOOP through the given linked list, reversing each prefix of the linked list one by one from the left. We discover the longest common list beginning with the reversed prefix and the list after the reversed prefix, after reversing a prefix.

Time complexity is O(n^2).

Implementation:

int calcCommon(NODE *x, Node *y){ int cnt = 0; // count common in the list starting // from node x and y while (1) { // increase the count by one for same VALUES if (x-&GT;value == y->value) cnt++; else break; x = x->next; y = y->next; } return cnt;}// Returns length of the longest palindrome sublistint maxPalindrome(Node *head){ Node *previous = NULL, *current = head; int answer = 0; // loop running till the end of the linked list while (1) { if(current==NULL) break; // reversed sublist from head to current Node *next = current->next; current->next = previous; // check for odd length palindrome answer = max(result, 2*calcCommon(previous, next)+1); // check for even length palindrome answer = max(result, 2*calcCommon(current, next)); // UPDATE previous and current for next iteration previous = current; current = next; } return answer;}

Discussion

5.	Given a value x and a sorted doubly linked list of different nodes (no two nodes have the same data). Count the number of triplets in the list that add up to x. The expected time complexity is O(n^2) and the expected space complexity is O(1).
Answer» Following the approach os using two POINTERS: From left to right, traverse the doubly linked list. Initialize two pointers for each current node during the traversal: first = pointer to the node next to the current node, and LAST = pointer to the list's last node. Count the NUMBER of PAIRS in the list that add up to the VALUE (x – the current node's data) from the first to the last pointer (algorithm described in Q8). This number should be added to the total count of triplets. Pointer to the last node can be retrieved only once at the beginning. Implementation: int pairCount(struct Node* num1, struct Node* num2, int val){ int cnt = 0; // The loop terminates when either of two the pointers // become NULL, or they cross each other or they become equal while (num1 != NULL && num2 != NULL && num1 != num2 && num2->next != num1) { // pair found if ((num1->value + num2->value) == val) { cnt++; // second is moved in backward direction num2 = num2->prev; // first is moved in forward direction num1 = num1->next; } // else first is moved in forward direction else if ((num1->value + num2->value) < val) num1 = num1->next; // if sum is greater than 'value' // second is moved in backward direction else num2 = num2->prev; } // required number of pairs return cnt;}// function to count triplets in a sorted DLL// whose sum equals a given value 'x'int tripletCount(struct Node* head, int x){ // check if the list is empty if (!head) return 0; int cnt = 0; struct Node* current = head; struct Node* last = head; struct Node* first; // get pointer to the last node of the doubly linked list while (last->next) last = last->next; // traverse the doubly linked list while (current) { // for every current node first = current->next; // count the number of pairs with sum(x - current->data) in the range // first to last and add it to the 'cnt' of triplets cnt += pairCount(first, last, x - current->value); current = current->next; } // required number of triplets return cnt;}

5.

Given a value x and a sorted doubly linked list of different nodes (no two nodes have the same data). Count the number of triplets in the list that add up to x. The expected time complexity is O(n^2) and the expected space complexity is O(1).

Answer»

Following the approach os using two POINTERS:

From left to right, traverse the doubly linked list. Initialize two pointers for each current node during the traversal: first = pointer to the node next to the current node, and LAST = pointer to the list's last node. Count the NUMBER of PAIRS in the list that add up to the VALUE (x – the current node's data) from the first to the last pointer (algorithm described in Q8). This number should be added to the total count of triplets. Pointer to the last node can be retrieved only once at the beginning.

Implementation:

int pairCount(struct Node* num1, struct Node* num2, int val){ int cnt = 0; // The loop terminates when either of two the pointers // become NULL, or they cross each other or they become equal while (num1 != NULL && num2 != NULL && num1 != num2 && num2->next != num1) { // pair found if ((num1->value + num2->value) == val) { cnt++; // second is moved in backward direction num2 = num2->prev; // first is moved in forward direction num1 = num1->next; } // else first is moved in forward direction else if ((num1->value + num2->value) < val) num1 = num1->next; // if sum is greater than 'value' // second is moved in backward direction else num2 = num2->prev; } // required number of pairs return cnt;}// function to count triplets in a sorted DLL// whose sum equals a given value 'x'int tripletCount(struct Node* head, int x){ // check if the list is empty if (!head) return 0; int cnt = 0; struct Node* current = head; struct Node* last = head; struct Node* first; // get pointer to the last node of the doubly linked list while (last->next) last = last->next; // traverse the doubly linked list while (current) { // for every current node first = current->next; // count the number of pairs with sum(x - current->data) in the range // first to last and add it to the 'cnt' of triplets cnt += pairCount(first, last, x - current->value); current = current->next; } // required number of triplets return cnt;}

Discussion

6.	Let's say there are two lists of varying lengths that merge at a certain point; how do we know where the merging point is?
Answer» You begin with List 1 and assume that the NULL at the end is a pointer to the start of List 2, giving the illusion of a cyclic list. After that, the algorithm will inform you how far down List 1 the merging is. Make an iterator pointer that runs forward until it reaches the end of the list, then jumps to the start of the opposite list, and so on. Make two of them, each pointing to two different heads. Each time you advance the pointers by one, they will eventually meet in the intersection point (IP). After one or two passes, this will occur. Count the number of nodes traversed from head1-> tail1-> head2 -> intersection point and head2-> tail2-> head1 -> intersection point to have a better understanding. Both will be equal (Draw diff types of linked lists to verify this). The reason for this is that both pointers must traverse identical distances (head1->IP + head2->IP) before returning to IP. As a result, by the time it reaches IP, both pointers will be equal, and we will have ARRIVED at the merging point. Node* getIP(Node* head1, Node* head2){ // two pointers ptr1 and ptr2 // at the heads of the two lists Node* P1 = head1; Node* p2 = head2; if (p1 == NULL \|\| p2 == NULL) return NULL; // the two lists are to be traversed until we reach the IP while (p1 != p2) { p1 = p1->next; p2 = p2->next; // When p1 reaches the end of the list, it is // redirected to head2. if (p1 == NULL) p1 = head2; // When p2 reaches the end of the list, it is // redirected to head1. if (p2 == NULL) p2 = head1; // If at any node p1 meets p2, we have got our IP. if (p1 == p2) return p2; } return p2;} OR Make a circular linked list by traversing the FIRST linked list (counting the ELEMENTS). (Keep track of the last node so we can break the circle later.) Reframe the issue as locating the loop in the second linked list. We already KNOW the length of the loop which is equal to the length of the first linked list. We have to traverse those many numbers of nodes in the second list first, and then another pointer should be started from the beginning of the second list. We have to continue traversing until they meet, and that is the required intersection point. The circle should be removed from the linked list. Both the approaches have O(n+m) time and O(1) space complexity.

6.

Let's say there are two lists of varying lengths that merge at a certain point; how do we know where the merging point is?

Answer»

You begin with List 1 and assume that the NULL at the end is a pointer to the start of List 2, giving the illusion of a cyclic list. After that, the algorithm will inform you how far down List 1 the merging is.

Make an iterator pointer that runs forward until it reaches the end of the list, then jumps to the start of the opposite list, and so on.
Make two of them, each pointing to two different heads.
Each time you advance the pointers by one, they will eventually meet in the intersection point (IP). After one or two passes, this will occur.

Count the number of nodes traversed from head1-> tail1-> head2 -> intersection point and head2-> tail2-> head1 -> intersection point to have a better understanding. Both will be equal (Draw diff types of linked lists to verify this). The reason for this is that both pointers must traverse identical distances (head1->IP + head2->IP) before returning to IP. As a result, by the time it reaches IP, both pointers will be equal, and we will have ARRIVED at the merging point.

Node* getIP(Node* head1, Node* head2){ // two pointers ptr1 and ptr2 // at the heads of the two lists Node* P1 = head1; Node* p2 = head2; if (p1 == NULL || p2 == NULL) return NULL; // the two lists are to be traversed until we reach the IP while (p1 != p2) { p1 = p1->next; p2 = p2->next; // When p1 reaches the end of the list, it is // redirected to head2. if (p1 == NULL) p1 = head2; // When p2 reaches the end of the list, it is // redirected to head1. if (p2 == NULL) p2 = head1; // If at any node p1 meets p2, we have got our IP. if (p1 == p2) return p2; } return p2;}

OR

Make a circular linked list by traversing the FIRST linked list (counting the ELEMENTS). (Keep track of the last node so we can break the circle later.)
Reframe the issue as locating the loop in the second linked list.
We already KNOW the length of the loop which is equal to the length of the first linked list. We have to traverse those many numbers of nodes in the second list first, and then another pointer should be started from the beginning of the second list. We have to continue traversing until they meet, and that is the required intersection point.
The circle should be removed from the linked list.

Both the approaches have O(n+m) time and O(1) space complexity.

Discussion

7.	Given two polynomial expressions represented by linked lists. You need to write a function that adds these lists, that is, adds the coefficients that have the same variable powers.
Answer» Implementation: struct NODE { int coefficient; int power; struct Node* next;};void createNode(int X, int y, struct Node** t){ struct Node v, z; z = t; if (z == NULL) { v = NEW Node; v->coefficient = x; v->power = y; t = v; v->next = new Node; v = v->next; v->next = NULL; } else { v->coefficient = x; v->power = y; v->next = new Node; v = v->next; v->next = NULL; }}// Function to add two polynomial expressionsvoid polyAdd(struct Node* poly1, struct Node* poly2, struct Node* poly){ while (poly1->next &AMP;& poly2->next) { // If the power of the 1st polynomial is greater than that of 2nd, // then store 1st as it is and move its pointer if (poly2->power &LT; poly1->power) { poly->power = poly1->power; poly->coefficient = poly1->coefficient; poly1 = poly1->next; } // If the power of the 2nd polynomial is greater than that of 1st, // then store 2nd as it is and move its pointer else if (poly1->power < poly2->power) { poly->power = poly2->power; poly->coefficient = poly2->coefficient; poly2 = poly2->next; } // If power of both polynomial expressions is same then // add their coefficients else { poly->power = poly1->power; poly->coefficient = poly1->coefficient + poly2->coefficient; poly1 = poly1->next; poly2 = poly2->next; } poly->next = new Node; poly = poly->next; poly->next = NULL; } while (poly1->next \|\| poly2->next) { if (poly1->next) { poly->power = poly1->power; poly->coefficient = poly1->coefficient; poly1 = poly1->next; } if (poly2->next) { poly->power = poly2->power; poly->coefficient = poly2->coefficient; poly2 = poly2->next; } poly->next = new Node; poly = poly->next; poly->next = NULL; }} Time Complexity: O(m + n), where m and n are the respective numbers of nodes in the first and second lists.

7.

Given two polynomial expressions represented by linked lists. You need to write a function that adds these lists, that is, adds the coefficients that have the same variable powers.

Answer»

Implementation:

struct NODE { int coefficient; int power; struct Node* next;};void createNode(int X, int y, struct Node** t){ struct Node *v, *z; z = *t; if (z == NULL) { v = NEW Node; v->coefficient = x; v->power = y; *t = v; v->next = new Node; v = v->next; v->next = NULL; } else { v->coefficient = x; v->power = y; v->next = new Node; v = v->next; v->next = NULL; }}// Function to add two polynomial expressionsvoid polyAdd(struct Node* poly1, struct Node* poly2, struct Node* poly){ while (poly1->next &AMP;& poly2->next) { // If the power of the 1st polynomial is greater than that of 2nd, // then store 1st as it is and move its pointer if (poly2->power &LT; poly1->power) { poly->power = poly1->power; poly->coefficient = poly1->coefficient; poly1 = poly1->next; } // If the power of the 2nd polynomial is greater than that of 1st, // then store 2nd as it is and move its pointer else if (poly1->power < poly2->power) { poly->power = poly2->power; poly->coefficient = poly2->coefficient; poly2 = poly2->next; } // If power of both polynomial expressions is same then // add their coefficients else { poly->power = poly1->power; poly->coefficient = poly1->coefficient + poly2->coefficient; poly1 = poly1->next; poly2 = poly2->next; } poly->next = new Node; poly = poly->next; poly->next = NULL; } while (poly1->next || poly2->next) { if (poly1->next) { poly->power = poly1->power; poly->coefficient = poly1->coefficient; poly1 = poly1->next; } if (poly2->next) { poly->power = poly2->power; poly->coefficient = poly2->coefficient; poly2 = poly2->next; } poly->next = new Node; poly = poly->next; poly->next = NULL; }}

Time Complexity: O(m + n), where m and n are the respective numbers of nodes in the first and second lists.

Discussion

8.	How will you find the length of a linked list which contains a cycle?
Answer» The algorithm to determine the length of the list: At a time, pointer A advances one node while pointer B advances two nodes. Starting from the head, they move until B reaches null (no loop) or A and B refer to the same node. Now, if A simply advances, A will run into B again. The length of the loop, let's CALL it X, may be calculated from this. Begin again from the head, but this time have a pointer C which has moved x nodes, followed by a pointer D behind it. Both will move one node further at a time. When they meet, the length of the linked list with a loop is equal to the number of nodes traversed by D PLUS x. int calcLen( Node* head ){ struct Node A = head, B = head; while ( A && B && B->next ) { A = A->next; B = B->next->next; /* If slow_p and fast_p meet at some point then there is a loop / if (A == B) { int x = 1; struct Node t = A; while (t->next != A) { x++; t = t->next; } } } struct Node C = head, D = head; int y = 0; for ( int i = 0; i < x; i++ ) { C = C->next; } while( C != D ) { y++; C = C->next; D = D->next; } RETURN x+y;} Time Complexity: O(n) Space Complexity: O(1)

8.

How will you find the length of a linked list which contains a cycle?

Answer»

The algorithm to determine the length of the list:

At a time, pointer A advances one node while pointer B advances two nodes.
Starting from the head, they move until B reaches null (no loop) or A and B refer to the same node.
Now, if A simply advances, A will run into B again. The length of the loop, let's CALL it X, may be calculated from this.
Begin again from the head, but this time have a pointer C which has moved x nodes, followed by a pointer D behind it. Both will move one node further at a time.
When they meet, the length of the linked list with a loop is equal to the number of nodes traversed by D PLUS x.

int calcLen( Node* head ){ struct Node *A = head, *B = head; while ( A && B && B->next ) { A = A->next; B = B->next->next; /* If slow_p and fast_p meet at some point then there is a loop */ if (A == B) { int x = 1; struct Node *t = A; while (t->next != A) { x++; t = t->next; } } } struct Node *C = head, *D = head; int y = 0; for ( int i = 0; i < x; i++ ) { C = C->next; } while( C != D ) { y++; C = C->next; D = D->next; } RETURN x+y;}

Time Complexity: O(n)
Space Complexity: O(1)

Discussion

Explore topic-wise InterviewSolutions in .

Given a linked list with each node representing a linked list and two pointers of its type given below. You need to flatten the lists into a single linked list. The flattened linked list also needs to be sorted. Discuss the approach.

In a standard Doubly Linked List, two address fields are required to contain the addresses of previous and next nodes. Can you create a doubly linked list using only one space for the address field with every node?

Given a singly linked list with an additional "arbitrary" pointer at each node that currently points to NULL. What algorithm will you implement to make the "arbitrary" pointer point to the next node with a greater value?

Given a linked list, find the length of the longest palindrome list that appears in that linked list using O(1) extra space.

Given a value x and a sorted doubly linked list of different nodes (no two nodes have the same data). Count the number of triplets in the list that add up to x. The expected time complexity is O(n^2) and the expected space complexity is O(1).

Let's say there are two lists of varying lengths that merge at a certain point; how do we know where the merging point is?

Given two polynomial expressions represented by linked lists. You need to write a function that adds these lists, that is, adds the coefficients that have the same variable powers.

How will you find the length of a linked list which contains a cycle?