- Create a dummy node and set its next pointer to the head of the linked list.
- Initialize two pointers,
first
andsecond
, to the dummy node. - Advance the
first
pointern + 1
nodes forward. - While the
first
pointer is not null:- Advance both the
first
andsecond
pointers one node forward.
- Advance both the
- Set the
next
pointer of thesecond
node to thenext
pointer of thesecond.next
node. - Return the next pointer of the dummy node.
The time complexity of the algorithm is O(n), where n is the length of the linked list. This is because the algorithm needs to traverse the linked list twice.
The space complexity of the algorithm is O(1), since it only needs to store three pointers.