13. DSA with C++ - Standard Questions on Linked Lists

Standard Questions on Linked Lists

Linked list questions are frequently asked in technical interviews, including those conducted by FAANG (Facebook, Amazon, Apple, Netflix, Google) and other top tech companies. Here are some standard questions on linked lists that often come up in interviews:

1. Reverse a Linked List:
   • Given a linked list, reverse the order of its nodes.
   • Example: Input: 1 -> 2 -> 3 -> 4 -> 5, Output: 5 -> 4 -> 3 -> 2 -> 1
2. Detect Cycle in a Linked List:
   • Determine if a linked list contains a cycle or not.
   • Example: Input: 1 -> 2 -> 3 -> 4 -> 5 -> 2 (Node with value 2 points back to Node with value 3), Output: true
3. Find the Middle Node of a Linked List:
   • Find the middle node of a linked list without knowing the length in advance.
   • Example: Input: 1 -> 2 -> 3 -> 4 -> 5, Output: Node with value 3
4. Merge Two Sorted Linked Lists:
   • Given two sorted linked lists, merge them into a single sorted linked list.
   • Example: Input: List 1: 1 -> 3 -> 5, List 2: 2 -> 4 -> 6, Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6
5. Remove Nth Node from the End of a Linked List:
   • Remove the Nth node from the end of a linked list and return the resulting list.
   • Example: Input: 1 -> 2 -> 3 -> 4 -> 5, N = 2, Output: 1 -> 2 -> 3 -> 5
6. Intersection of Two Linked Lists:
   • Find the node at which two singly linked lists intersect, if they do.
   • Example: Input: List 1: 1 -> 2 -> 3 -> 4, List 2: 6 -> 7, Intersection: 3 -> 4
7. Palindrome Linked List:
   • Check if a linked list is a palindrome (reads the same forward and backward).
   • Example: Input: 1 -> 2 -> 3 -> 2 -> 1, Output: true