1) Let X be the length of the first linked list until intersection point.
Let Y be the length of the second linked list until the intersection point.
Let Z be the length of the linked list from intersection point to End of
the linked list including the intersection node.
We Have
X + Z = C1;
Y + Z = C2;
2) Reverse first linked list.
3) Traverse Second linked list. Let C3 be the length of second list - 1.
Now we have
X + Y = C3
We have 3 linear equations. By solving them, we get
X = (C1 + C3 – C2)/2;
Y = (C2 + C3 – C1)/2;
Z = (C1 + C2 – C3)/2;
4) Reverse first linked list.

Guys , i dont understand this method. I mean, why do we reverse the first linked list at all ?
And how do we know C3 ???? isnt that the question ?

Recommended Answers

All 6 Replies

Maybe you don't understand it because the problem is poorly worded.

Maybe you don't understand it because the problem is poorly worded.

ya, its just written in a confusing manner. Sir, can u please tell me the algo in a better way.
Why reverse ? and the part about C3

What is the "intersection point" of two linked lists?

Edit: Oh, you have two linked lists that share a common node (and all the nodes after that). Then this algorithm makes perfect sense.

please can u tell me what do we gain by reversing the ll . I mean still C1 ,C2,
C3 remain same right. ????

I think you are confused because you are considering the lists as 2 separate lists, when they are actually more like a Y shape. For example, let's take these as the two lists:

List 1 = 1->2->3->5->10
List 2 = 4->7->3->5->10

So following your steps we get:
Step 1:
X + Z = C1 = 5
Y + Z = C2 = 5

Step 2:
List 1 = 10->5->3->2->1

Step 3: This is where you are becoming confused by thinking of the lists as separate lists. We'll now traverse the 2nd list counting nodes as we go
Step 3.1: 1st node is 4, count is 1
Step 3.2: 2nd node is 7 (4 -> 7), count is 2
Step 3.3: 3rd node is 3 (7 -> 3), count is 3
Step 3.4: 4th node is 2 (3 -> 2), count is 4 <- This is where the magic happens, see * below
Step 3.5: 5th node is 1 (2 -> 1), count is 5

* Remember, we reversed the first list which changes what node comes next. Since the nodes are shared, reversing the first list also modifies the second list.

X + Y = C3 = 4 (count-1 from above).

The rest is just math.

commented: Good interpretation of a clever (and poorly described) algorithm. +2

Momerath, thanks a lot. U really understood where i was facing the problem.
Yes, i was not able to visualize that even second ll also gets affected.
Now i am . Thanks again.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.