I wrote this up in an email to myself a while ago but I figure I’ll post it up here too. A very common programming interview question is how to reverse a singly linked list. I’ve gotten this in two interviews and also in an algorithms problem set once.
Here are my solutions, both an iterative and a recursive approach. I think I’ve tested both out pretty well but please do let me know if you break either one 🙂 . Also, I use a class called ZNode which is just an ordinary node class, just cooler because it has a “Z” in it.
Iterative:
basically go from head to end, reversing as you go by using 3 pointers to: theHead, revHead, and hold (actually the names are pretty arbitrary).
//Iterative ZNode reverseIter(ZNode head) { ZNode theHead = head; if(theHead.getNext() == null) { return theHead; } ZNode revHead = theHead.getNext(); ZNode hold = revHead; while(hold != null) { hold = hold.getNext(); revHead.setNext(theHead); //set the next of the head of the list to null if(theHead == head) { theHead.setNext(null); } theHead = revHead; revHead = hold; } return theHead; }
Recursive:
Start at the head and keep going until you hit the end, then go backwards setting each node’s next field to its parent. Each recursive call has the parameters: head, parent, and revHead (the head of the new reversed list)
//Recursively ZNode reverse(ZNode head) { return reverseHelper(head,null,null); } ZNode reverseHelper(ZNode head, ZNode parent, ZNode revHead) { if(head.next == null) { head.setNext(parent); revHead = head; return revHead; } else { revHead = reverseHelper(head.getNext(),head, revHead); head.setNext(parent); return revHead; } }
Leave a Reply