Understanding the two pointer pattern

To perform any operation on the data items in a singly linked list, we must traverse it from head to tail and find those items. A doubly linked list, however, can be traversed in two directions, i.e., either from head to tail or tail to head, and depending on the problem, we may choose one direction over the other.

However, some problems require us to traverse the linked list in both directions simultaneously. While this is impossible with singly linked lists, we can simultaneously traverse in both directions in a doubly linked list using the two-pointer technique. The two-pointer traversal technique allows us to solve certain problems in linear time and single-pass, which would otherwise require inefficient nested loops.