###### tags: `leetcode` `recursive`
# 21. Merge Two Sorted Lists

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        def f(cur, l1, l2):
            print(l1 != None, l2 != None)
            print(l1)
            print(l2)
            if l1 != None and l2 != None:
                if l1.val <= l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
                f(cur, l1, l2)
                
        dh = ListNode(-1)
        cur= dh  # dummy head
        f(cur, l1, l2)
        
        print(l1 != None, l2 != None)
        print(l1)
        print(l2)
        if l1 == None:
            print("no l1", l2)
            cur.next = l2
        if l2 == None:
            cur.next = l1
            print("no l2", l1)
        return dh.next

The `l1` and `l2` after `f()` is still the same as original.

How to make the manipulation on `l1` and `l2` in `f()` be permanent, even after `f()` is finished?

## h2
# Iterative

- Need three pointers, why three?
- We will definitely do: [`previous_node.next`](http://node.next) ←`a_node_from_list_1`
- and also do: [`previous_node.next`](http://node.next) ←`a_node_from_list_2`
- So, three pointers.
- Create a dummy head or compare to know the first node.
- A dummy head sometimes is the core to solve a problem.
- Compare the heads of two LLs, take the larger, attach to answer_LL
- If one LL is depleted, attach the other whole LL to eh answer_LL

# recursive

- scratch an outline, the main code calling the recursive soln(); or recursive helper inside soln()
- depends if we need pre/post-process which should not be recursive
- how to connect caller and the called
- need to collect all output of the called, and then combine? // will it fanout?
- combine: AND OR sum() multiply()
- or we only need one among branches
- or we use global var accessible by all recursive children to store answer
- global var as inputreference data/
- be caution of name scope, pass/copy by value or by reference
- counting down
- termination/base case
- memorization/cache

def soln(LL1, LL2):
		def helper(???):
				if is_termination:
						# do things
						return foo
				else:
						# do things
						return helper(??? +-*/ $$$) +-*/ @@@
		# can put to main snippet	
	  # some preprocessing, only once. Shall not in recursion.
		helper_output = helper(...)
		# some postpocessing, only once. Shall not in recursion.
		return answer

if __name__ == "__main__":
		LL1 = ...
		LL2 = ...
		answer_LL = soln(LL1, LL2)
		print(anser_LL)

def soln(LL1, LL2):
		if is_terminated:
				# do things
				return base_case
		else
				# do things
				return soln(altered_input) +-*/ sth
if __name__ == "__main__":
		LL1 = ...
		LL2 = ...
		answer_LL = soln(LL1, LL2)
		print(anser_LL)

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2