More linked list problems

There are a lot of commonly asked linked list questions. They can range from simple to much more challenging. The following are some questions that can all be solved using two pointers ptr1 and ptr2 with different moving speed. They are relatively simple so I won`t post code here, but just the method:

Find the middle element of a linked list.

Let ptr1 moves 1 step and ptr2 moves 2 steps in each loop. When ptr2 reaches the end, ptr1 is pointing the middle element. 

Find the nth last element of a linked list.

Let ptr2 move n steps ahead first, and then let two pointers move together. When ptr2 reaches the end, ptr1 is pointing the nth last element.

Two linked lists of different length intersect at one node. Find this node.

We should first find the lengths of two linked lists by iterating through the whole list. Suppose the length of two lists are len1 and len2, len1 < len2, the difference d = len2 - len1. Now reset two pointers and let the pointer of longer list move d steps first. Then move two pointers simultaneously and compare the data of them. When data is equal, we find the node.

Given a circular linked list, find node at the beginning of the loop.

Let N be the node we want to find. In each loop, ptr1 moves 1 step and ptr2 moves 2 steps, until they meet at one node. The distance from this node to N is equal to the distance from head node to N. Now we reset ptr1 to head node and begin to move two pointers simultaneously. When they meet again, N is found there.