Given two sorted linked lists. Find the path of maximum sum.

Given two sorted linked lists. You start with a one of the two lists and then move till the end. You may switch to the other list only at the point of intersection (which mean the two node with the same value in different lists.) You have to find the path of maximum sum.

Eg
  1->3->30->90->120->240->511
  0->3->12->32->90->125->240->249
  You can switch at 3 90 or 240 so the max sum paths is
  1->3->12->32->90->125->240->511 

Sol:

This can be solved in O(m+n).

Take two pointers p1 and p2 for both lists. 

Maintain two sums curr1 and curr2 for each list init to 0.

1. If p1 == p2: 
• if curr1 > curr2: Choose LL1 as path upto this point.
• else: Choose LL2 as path.
2. If p1 < p2:
• curr1 += p1
• increment p1 to next node.
3. else if p2 < p1:
• curr2 += p2
• increment p2 to next node
4. if p1 == null:
• traverse all of p2 and keep incrementing curr2.
• Take the path with greater sum
5. if p2 == null: // do as above for p1

https://www.geeksforgeeks.org/flipkart-interview-set-7-sde-ii/