To insure that you all will learn something…

I am studying to take my insurance licensing exam for the second time :-p and I thought hey why not write some entries about the insurance stuff I learn.  Hopefully I may learn the material better if I try to summarize all the rules in my own words and make them a little bit more riveting for my readers.  Hopefully you all will learn something and not fall asleep :D.  Tune in tomorrow for the first post(s)!

Advertisement

 

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

 

zarg things i need to do this week {10/1/07-10/7/07}

Man, this is kind of depressing.

Monday

• Organize notebooks (finally)
• LC211 HW
• CS113 Cheat Sheet
• Compare Cheat Sheets
• Family dinner
• CS113 HW?
• Study for CS113 Exam 1

Tuesday

• CS113 Exam 1
• LC211 Composition
• Study for LC211 L29 Quiz makeup?
• Trivia Practice?
• CS113 HW?
• Study for CS210 (figure out programming problems)

Wednesday

• Unit Testing Lab?
• CS113 HW?
• Finance club?
• Study for CS210!

Thursday

• CS210 Exam 1!
• MMOGS?
• CS440 Project 2!

Friday

• LC211 L30 quiz?
• CS440 Project 2!

Saturday

• Dad’s Birthday
• Zoo

Sunday

• Dave Mackey’s house

Monday

• CS210 HP Project?