InterviewSolution
| 1. |
How To Find Middle Element Of A Singly Linked List In One Pass? |
|
Answer» You should clarify what does mean by one pass in this question. If Interviewer says that you cannot loop twice and you just have to USE one loop, then you can use the two pointer approach to solving this PROBLEM. In the two pointer approach, you have two pointers, fast and slow. In each step, the fast pointer moves two nodes, while slow pointer just steps one node. So, when fast pointer will point to the last node i.e. where next node is NULL, the slow pointer will be pointing to the middle node of the LINKED list. You should clarify what does mean by one pass in this question. If Interviewer says that you cannot loop twice and you just have to use one loop, then you can use the two pointer approach to solving this problem. In the two pointer approach, you have two pointers, fast and slow. In each step, the fast pointer moves two nodes, while slow pointer just steps one node. So, when fast pointer will point to the last node i.e. where next node is null, the slow pointer will be pointing to the middle node of the linked list. |
|