1. Find the nth element from the end of a singly linked list.
Approach 1: Traverse the list and find the length L of the list. Traverse the list second time and find (L-(n-1))th element from the head/start of the linked list. Total traversal cost (L-n+1).
Approach 2: Take two pointers A and B. Initialize both pointers to the head of the list. First move B to point to the nth node in the list. Next, move both pointers A and B together. Terminate the process when B points to the last node. At termination. A points to the nth node from the end of the linked list.
2. What are important types of linked lists.
Singly Linked List, Doubly Linked List, XOR-Linked List, and Circular Linked List.
3. Given a circular linked list (singly-connected) and a pointer (head) to a node in the list , insert a node just before the head without fully traversing the list.
Hint: Insert a node after the head, switch values of head node and new node, move the head to next
4. Give an algorithm to find if a linked list is circular or not.
5. Give an algorithm to find if a linked list has a cycle/loop.
Floyd's Cycle Detection Algorithm
Some other solutions
6. How to construct an efficient doubly-connected linked list.
Hint: XOR-Linked List
7. Given a forked linked list, find the point of fork.
G---H---I
|
A---B---C---D---E---F---J---K---L--M
In the above forked linked list, we see that J is the forking point.
8. Code to simulate Josephus problem.
Hint: Use circular linked list.
Approach 1: Traverse the list and find the length L of the list. Traverse the list second time and find (L-(n-1))th element from the head/start of the linked list. Total traversal cost (L-n+1).
Approach 2: Take two pointers A and B. Initialize both pointers to the head of the list. First move B to point to the nth node in the list. Next, move both pointers A and B together. Terminate the process when B points to the last node. At termination. A points to the nth node from the end of the linked list.
2. What are important types of linked lists.
Singly Linked List, Doubly Linked List, XOR-Linked List, and Circular Linked List.
3. Given a circular linked list (singly-connected) and a pointer (head) to a node in the list , insert a node just before the head without fully traversing the list.
Hint: Insert a node after the head, switch values of head node and new node, move the head to next
4. Give an algorithm to find if a linked list is circular or not.
5. Give an algorithm to find if a linked list has a cycle/loop.
Floyd's Cycle Detection Algorithm
Some other solutions
6. How to construct an efficient doubly-connected linked list.
Hint: XOR-Linked List
7. Given a forked linked list, find the point of fork.
G---H---I
|
A---B---C---D---E---F---J---K---L--M
In the above forked linked list, we see that J is the forking point.
8. Code to simulate Josephus problem.
Hint: Use circular linked list.
