Reversing a Linked List

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;
		}
	}

Advertisement