【第三轮】6.23-6.29 CareerCup 2.3

chouclee 发表于 2014-7-4 22:54
java都是传值引用（“Java is always pass-by-value” http://stackoverflow.com/questions/40480/is-jav ...

等于是复制了一个node Class。
然后就跟c里面的指针一样，node = node.next 只是指针后移。。

guchang 发表于 2014-7-2 14:24
解题思路】
  把指定node后一个node的data 和next付给指定node

额0。0用node = node.next只是把pointer指向了下一个节点而已。。。对整个LinkedList其实没有任何影响

the problem is a little ambiguous, in the first time, what I understand is giving an input LinkedList and delete the middle node of the LinkedList. But actually, the true meaning is, just giving you a pointer to a node of a LinkedList, you should delete it and you can only access to that node.

In the solution below, I implement both the idea.

Question1
Problem: giving you a pointer to a node of a LinkedList, you should delete it and you can only access to that node

Solution
Before writing code, you should first consider the situation: what if the node to be deleted is the last node in the LinkedList? How to you handle it?

According to the description in the Book:

Note that this problem cannot be solved if the node to be deleted is the last node in the linked list. That’s ok—your interviewer wants you to point that out, and to discuss how to handle this case. You could, for example, consider marking the node as dummy.
In my solution, if the delete node is the last node, I just mark the value of the value of the node as MIN_VALUE and don’t print out.

Idea:
1) copy the next value to current
2) point current next to next’s next

Question2
Problem2: giving an input LinkedList and delete the middle node of the LinkedList

Solution
Before writing code, you should consider the situation below and ask the interviewer first!
1) what if the length of the input LinkedList is even like a->b->c->d?
2) in 1), if the requirement is to delete the c rather than b, what should you do?
3) If there is just two node in the input, what should we do?

Idea: two pointers, one runs slow, one runs fast(every time moves two node)

In the implementation below
1) I use the deleteNode() method in the Question1, if you don’t want to use the method, you should let the fast node go one step first, so that the slow pointer will at the previous node of the middle node, and using slow.next = slow.next.next to delete the middle node
2) When the length of the input LinkedList is even, for example, a->b->c->d, I just define the node b as the middle node. If define the C as the middle node, how do you change the code to implement it?

Time Complexity: O(n)
Space Complexity: O(n)

Code:
http://www.jyuan92.com/post-446