academic


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)!

Advertisements

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

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?