Linked List Problems

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.