linked lists

Question 1

How do you reverse a linked list? (iterative)

Answer 1

Init 3 pointers, null, current, prev. While current is not null, set next to current.next. Set current.next to prev. Set prev to current. Set current to next.

Question 2

How do you reverse a linked list? (recursive)

Answer 2

divide list into two parts, head node and rest of list. call reverse for rest of the linkedList. Link the rest to the first.
fix head pointer

Question 3

Find intersection of two linked lists

Answer 3

Draw them out, being careful not to make them the same length. Notice that if there is an intersection, they will end on the same node.

1. Run through each LL to get lengths and tails
2. Compare tails, if different, return immediately
3. Set two opinters to start of each LL
4. On longer LL, advance its pointer by diff in lengths
5. Traverse each LL until pointers are the same.