JZ014-合并两个排序的链表

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

示例：

输入

node1: 1 -> 3 -> 5 -> 7 -> 9 

node2: 2 -> 4 -> 6 -> 8 -> 10

输出

result  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

链表是由一系列连接在一起的结点构成，其中的每个结点都是一个数据结构。

        这道题属于链表题型中等题目，做法很简单 ,大致思路如下：

第一种方法：常规方法，

      ①创建新的链表头pre，用于存储result链表

      ②两个链表同时遍历，按照下图所示进行连接链表

      ③返回pre链表头，此时pre就是合并好的新链表

第二种方法：递归，写递归的代码很简单，最重要的要明白递归函数的功能。可以不必关心递归函数的具体实现。
比如这个ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
函数功能：合并两个单链表，返回两个单链表头结点值小的那个节点。

方法一：

方法二：

       思考为什么他可以写出这么好的代码，把每道题的思路理解后用笔记本记录下来，争取刷到融会贯通，即看见有个题能自动归类到某个方面，这样有一定好处。面试最重要的是让面试官日后能愿意与你以后一起工作，因此沟通交流非常重要。比如有时候面试需要交流，看着像是一道排序的题做不出来，就可以跟面试官交流：“我有几个不成熟的想法，一排序，二动态规划，三是直接搜索算法”，面试官可能就给个提示：“你先用排序试试吧“。