Double connection illustration
I am trying to illustrate the double join problem. this is from an old test I've been studying lately.
The question is as follows:
draw the final link after this code:
ListNode n1 = new ListNode();
ListNode n2 = new ListNode();
ListNode n3 = n1;
n1.next = n2;
n3.prev = n1;
n1.next.prev = n3.next;
When I get lost this is the last line of code.
n1.next.prev = n3.next;
here's the solution:
http://www.imagechicken.com/viewpic.php?p=1242322384048558300&x=jpg
Can anyone walk me through this or lead me in a good direction?
a source to share
The key to this is that n1 and n3 point to the same ListNode.
Here are the states after each of the three operations:
n1.next = n2;
// n1.prev = null;
// n1.next = n2;
// n2.prev = null;
// n2.next = null;
// n3.prev = null;
// n3.next = n2;
n3.prev = n1;
// n1.prev = n1;
// n1.next = n2;
// n2.prev = null;
// n2.next = null;
// n3.prev = n1;
// n3.next = n2;
n1.next.prev = n3.next;
// n1.prev = n1;
// n1.next = n2;
// n2.prev = n2;
// n2.next = null;
// n3.prev = n1;
// n3.next = n2;
So in this last statement is the n3.next
same as n1.next
, which is n2
. Thus, the last statement is equivalent to settings n2.prev = n2
.
a source to share
Step one: two nodes are not connected. n1
also known as n3
.
+ ------- + next + ------- + next
| + ----> | + ---->
prev | n1 | prev | n2 |
<---- + n3 | <---- + |
+ ------- + + ------- +
Step two: n1.next = n2;
+ ------- + next + ------- + next
| + -----------> | + ---->
prev | n1 | prev | n2 |
<---- + n3 | <---- + |
+ ------- + + ------- +
Step three: n3.prev = n1;
Since n3
n1
, this turns the arrow around.
+ ------- + next + ------- + next
| + -----------> | + ---->
prev | n1 | prev | n2 |
/ ---- + n3 | <---- + |
\ ---> + ------- + + ------- +
Step four: n1.next.prev = n3.next;
Remember that n1.next
- n2
, a n3
- n1
. Follow the arrows:
+ ------- + next + ------- + next
| + -----------> | + ---->
prev | n1 | prev | n2 |
/ ---- + n3 | / ---- + |
\ ---> + ------- + \ ---> + ------- +
So the pointers prev
n1
and n2
both point to themselves.
a source to share
I would try drawing three boxes. Divide each box by a third - one third for the label, one third for "prev" and one third for "next". Then draw connecting lines from all "prev" and "next" to the corresponding label to see how everything is connected.
A picture can be worth a thousand words.
a source to share
This behavior is confusing until you realize that there are only two INSTANES from the ListNode; n1, n2, and n3 refer to these instances. And in particular, n1, n2, and n3 are set only once; since n3 is set to n1, you can just as easily replace n3 with n1 in this code and it will work the same.
a source to share