question
Given a singly linked list and its head node, find the node one-fourth of the way
to the end of the list.
ex. If there are n nodes, return the node at floor(n / 4). If n <= 4 return the first node.
ex. If there are n nodes, return the node at floor(n / 4). If n <= 4 return the first node.
Try using 2 pointers to walk through the list.
Thanks to subscriber Brett Olsen for pointing out an error in answer!
Use two pointers to iterate through the list, moving the second pointer to iterate through the list at four times the speed of the first. We do this by only incrementing the second pointer every fourth turn. At the end of the iteration, return the second pointer which will point to the solution one-fourth of the way through. This solution runs in O(n).
findQuarterNode(Node head)
Node w1 = head;
Node w2 = null;
int i = 0;
while (w1.next != null)
w1 = w1.next;
i++;
if (i == 4)
if (w2 == null)
w2 = head;
else
w2 = w2.next;
i = 0;
if (w2 == null)
return head;
return w2;
Use two pointers to iterate through the list, moving the second pointer to iterate through the list at four times the speed of the first. We do this by only incrementing the second pointer every fourth turn. At the end of the iteration, return the second pointer which will point to the solution one-fourth of the way through. This solution runs in O(n).