Cracking the Coding Interview Chapter 2 Java Solutions - Link Lists
These examples are dealing with Linked Lists. Remember to ask if singly or doubly linked, if you have a pointer to previous, if not then keep track of it. Using a slow and fast runner solves many problems, consider it. Also pay special attention to using recursion to "see into the future", as in make it to the end of a list and start counting backwards (see q2 and q7).
Ch02Ex01: Remove duplicates from a linked list with and without a temp variable
If you're working with a sindly linked list you don't have access to the previous pointer. So keep track of the previous node so you can delete the current by unlinking. A few things I forgot about when working it.
This is a good example of O(n) and O(n^2)
- Forgot to ask if I have a ref to the prev node. Much eaiser if I do, then no messing with two pointers.
- Welp, I miss read twice, this is a singly linked list, and even at that I had a bug because I forgot to update the previous pointer..
Good warmup, forgot a lot of the little things. Output...
Remove with a buffer a -> b -> a -> c -> d -> e -> a -> b a -> b -> c -> d -> e Now remove without buff a -> b -> a -> c -> d -> e -> a -> b a -> b -> c -> d -> e
Ch02Ex02: Find nth to last element in a linked list
Important, you'll probably think of the two pointer solution first, but you can actually do this recursivly. Great trick for other problems. Recursive jump down and increment the counter, when you start jumping back down the stack check if your end is equal to your last position. Otherwise just use the two pointer method. Create another pointer and fast forward it.
My solution for the recursive way, we tally up count as we move along.
private void getNthToLastRecursive(Node head, int k, int count) {
if (head.next == null) {
return;
}
getNthToLastRecursive(head.next, k, ++count);
if ( k == count - k ) {
System.out.println("The " + k + " to last node recursive is: " + head.value);
}
}
The books way is a little more clever, return zero when you hit the end, then start incrementing till it's equal to you nth node.
private int nthToLastBook(Node head, int k) {
if ( head == null ) {
return 0;
}
int i = nthToLastBook(head.next, k) + 1;
if ( i == k ) {
System.out.println("The " + k + " to last node books way is: " + head.value);
}
return i;
}
When solving with the runner method, I had to count on my fingers and be precise about where the runner variable would end up, be careful take your time.
a -> b -> a -> c -> d -> e -> a -> b The 3 to last node iterative is: e The 3 to last node recursive is: e The 3 to last node books way is: e
Ch02Ex03: Delete element in a LinkedList given access only to that element
Ok, did two dumb things when starting this question. Started solving this with a previous pointer, which is NOT what the question asked, then I started writing a method that copies each next value into the current. Really I just need to get rid of one. Would have been easy to see if I whiteboarded that. Need to remember to whiteboard first. Draw it out, come up with a solution, then imlement that in code...
So just copy the next into the current. If you check the edge cases, like you should, you would see that you can't delete the last one. I print a message for that.
private void deleteNodeAt(Node node) {
if (node.next == null) {
System.out.println("We can't delete the last node with this method");
}
if (node.next != null) {
node.value = node.next.value;
node.next = node.next.next;
}
}
a -> b -> a -> c -> d -> e -> a -> b We will delete node: c a -> b -> a -> d -> e -> a -> b We will delete node: b We can't delete the last node with this method
Ch02Ex04: Partition a linked list around a value
This one starts off pretty easy, I figured two stacks, one for the lower values, one for the higher, then join them up. Using java.util.Stack can be a little fussy since the pop method throws an EmptyStackException. So check empty() in the while loop. Another gotcha was the last element in my lessThan stack had to have it's next element set to null.. Otherwise I ended up with an infinite loop.
Another trick which the book mentions that I think is important. The easiest place to keep track of the end of a stack or linked list is right after you update it. This would have kept my stack popping code cleaner...
private Node partitionAround(Node head, String d) {
Stack<Node> lessThan = new Stack();
Stack<Node> greaterThan = new Stack();
while (head != null) {
int cur = (int) head.value.toCharArray()[0];
int val = (int) d.toCharArray()[0];
if ( cur < val ) {
lessThan.push(head);
}
else {
greaterThan.push(head);
}
head = head.next;
}
Node startLt = null;
Node endLt = null;
while (!lessThan.empty()) {
if ( startLt == null ) {
startLt = lessThan.pop();
endLt = startLt;
}
else {
endLt.next = lessThan.pop();
endLt = endLt.next;
}
}
endLt.next = null;
Node startGt = null;
Node endGt = null;
while (!greaterThan.empty()) {
if ( startGt == null ) {
startGt = greaterThan.pop();
endGt = startGt;
}
else {
endGt.next = greaterThan.pop();
endGt = endGt.next;
}
}
endGt.next = null;
endLt.next = startGt;
return startLt;
}
My output...
a -> b -> a -> c -> d -> e -> a -> b b -> a -> a -> b -> a -> e -> d -> c
One last note, I tried doing this in place... It's possible, but lots of pointers, and it got pretty hairy. I struggled with it, but if I would have actually walked throught the processes in place on my white board before coding the solution (and hoping to find edge cases there), I would have saved lots of time. That incomplete code looked a little like this..
f(Node h, int v) {
Node p = null;
node c = n ;
while( c!=null) {
Node n = c.next;
Node r= h;
while( r!= null){
if (r.value < p) break;
if (r.value == v) {
p.next = n;
c.next = r.net;
r.next = c;
break;
}
r = r.next;
}
p = c;
c = c.next; //something's up here
}
}
Ch02Ex05: Add values from two linked lists together
First off I read this problem wrong and solve it for one linked list, by leveraging how the base10 numbering system works. Personally I think this solution is HELLA important and you should know it. Wrap your brain around this...
private int listSum(Node head) {
int sum = 0;
int i = 0;
while (head != null) {
sum += ((Integer) head.value) * Math.pow(10, i);
i++;
head = head.next;
}
return sum;
}
Short and sweet. Modifying that to add two numbers up was a snap.
public int addListsJm(Node n1, Node n2) {
int v1 = listSum(n1);
int v2 = listSum(n2);
return v1 + v2;
}
Then I noticed the book solved it completely differently. This recursive function is a big WTF in my opinion, so I set about to solve it in an iterative fashion. Long story short, if you did the math by hand, you would have remembered to "carry the one over", and that's how this solution works. Take two numbers add them together, if they're greater than 10 then carry the one over to the next calculation.
And that's another reason to really really really just solve without code first. It's amazing how much you can solve with just some common sense, and then translating that into code.
public Node addNodesIter(Node n1, Node n2) {
Node rtn = null;
Node end = null;
int carry = 0;
while ( n1 != null && n2 != null && carry == 0) {
int v1 = n1 != null ? (int) n1.value : 0;
int v2 = n2 != null ? (int) n2.value : 0;
int sum = v1 + v2 + carry;
if ( sum >= 10 ) {
sum = sum %10;
carry = 1;
}
else {
carry = 0;
}
if (rtn == null) {
rtn = new Node(sum);
end = rtn;
}
else {
end.next = new Node(sum);
end = end.next;
}
n1 = n1.next != null ? n1.next : null;
n2 = n2.next != null ? n2.next : null;
}
return rtn;
}
Just for fun here's a picture from solving this on my whiteboard
Ch02Ex06: Find the start of a looped linked list
I honestly HATE this question. I can follow it up to a certain point, but then I go absolutly brain dead. I understand if slow is at the start of the list, then fast is k nodes into the list. Ok, then I know that loop_size - k, represents the total nodes left in the loop. They move one closer to each other every iteration of the loop, which means there are loop_size - k iterations before they meet again (because they get one closer to each other every iteration after entering the loop). Somehow that means they always meet k before the start of the loop and there's what I don't get. However given that piece of knowlege, here we go with an algo..
private void findLoopStart(Node head) {
Node slow = head;
Node fast = head;
while ( fast != null ) {
slow = slow.next;
fast = fast.next.next;
if ( slow == fast ) {
break;
}
}
fast = head;
while ( fast != slow ) {
slow = slow.next;
fast = fast.next;
}
System.out.println("Loop starts at node:" + slow.value);
return;
}
Ch02Ex07: Is a linked list a palendrome
Compared to coming up with a Floyd's Cycle Detection algorhythem on your own, this problem is a breeze. I used a stack, and the only real issue is dealing with even and odd sized palendromes.
private boolean isLlPalendrome(Node head) {
Node current = head;
Stack stack = new Stack<>();
int count = 0;
while ( current != null ) {
count++;
stack.push( (Character)current.value );
current = current.next;
}
int half = count / 2;
int count2 = 1;
current = head;
if ( count % 2 != 0 ) {
half++;
}
while ( current != null ) {
if ( count2 <= half ) {
stack.pop();
}
else {
if ( current.value != stack.pop() ) {
return false;
}
}
count2++;
current = current.next;
}
return true;
}
Output...
a -> b -> b -> a Is it a palendrome? true a -> b -> c -> b -> a Is it a palendrome? true a -> b -> c -> a Is it a palendrome? false
Of course if it seems to easy, it problably is. If we're not allowed to use something like a stack, then you could probably get pretty fancy with these options.
- Remember slow and fast runner solve lots of LL problems. How does that help here? Add to the stack until the fast runner is at the end, then compare stack to the everything after slow runner.
- Much like the solutions to find nth to last element, you can use recursion to essentially see into the future, falling back till you arrive at the halfway point of the code.