Programming Interviews Exposed Java Solutions Chapter 04 - Linked Lists

This is probably my favorite book in regards to coding interviews.  If you're having trouble with Cracking the Coding interview, then this a MUCH better place to start.  The explainations are top notch and they actually guide you through the thought process of solving these questions.  Highly recommend.

Here's a list of my solutions to these problems.  And of course, I always recommend getting the book yourself, and answering the questions.  You won't learn anything just reading these.

01. Describe a stack, then design a stack with an interface

This is a self contained example, run it from here.  Implementation of the interface here.

02. Create your own stack, and implement remove and insertAfter methods

My implementation creates a linked list like a->b->c->d->e.  Head and tail are in the main class.  The trick is to be careful with the pointers, draw it out on the whiteboard, a visual represenation will help you.

04. Find the M-th to last in a linked list

Solution?  Two pointers, fast forward the first M positions, start iterating as seen here.  

05. Flatten a linked list with child nodes

This one can be pretty difficult, in my solution I visit the nodes recursively and keep a pointer the next node so I can "fast forward" to it.

07. Determine if a linked list is circular

Can you find if iterating a linked list will create an infinite loop?  Adding an isVisitied node is a common way of solving this problem.  Matter of fact, if somebody comes up with the two pointer solutions right off the bat, that usually means they've seen this one already. Solution here.