解题思路：
1.非递归解法：类似于归并排序第二步合并的步骤，设置三个指针p1、p2、p3。p1指向第一个链表的头结点，p2指向第二个链表的头结点，p3指向第三个链表的头结点。首先确定第三个链表的表头指针list3Head。然后比较p1和p2所指向的值哪个小，就选择小的那个加入到第三个链表中，同时将指向较小元素的指针后移，p3也后移，重复上述操作，直到遍历完某一个链表为止。若另一个链表中此时还剩元素未遍历，则将剩余元素全部添加到新链表中。
2.递归解法：设置合并后链表的头结点pMergeHead初始值为null，从list1和list2的头结点开始，哪个链表指向的元素小，则将pMergeHead指向该节点，然后从较小的链表的下一个元素开始，递归地调用merge()方法。
/** * 剑指offer面试题17 合并两个排序的链表 */ class ListNode { int val; ListNode next = null; public ListNode(int val) { this.val = val; } } public class Solution { /** * 非递归实现 */ public static ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null && list2 == null) { return null; } if (list1 == null) { return list2; } if (list2 == null) { return list1; } //list和list2都不为空的情况下，利用归并排序中归并的思想 ListNode p1 = list1; ListNode p2 = list2; ListNode list3Head = null; //一开始需要确定新链表头指针的位置 if (list1.val < list2.val) { list3Head = new ListNode(list1.val); p1 = p1.next; } else { list3Head = new ListNode(list2.val); p2 = p2.next; } ListNode p3 = list3Head; while (p1 != null && p2 != null) { if (p1.val < p2.val) { //如果p1指向元素比p2小，则将p2指向元素加入到新链表中 ListNode temp = new ListNode(p1.val); p3.next = temp; p1 = p1.next; p3 = p3.next; } else { ListNode temp = new ListNode(p2.val); p3.next = temp; p2 = p2.next; p3 = p3.next; } } while (p1 != null) { ListNode temp = new ListNode(p1.val); p3.next = temp; p1 = p1.next; p3 = p3.next; } while (p2 != null) { ListNode temp = new ListNode(p2.val); p3.next = temp; p2 = p2.next; p3 = p3.next; } return list3Head; } /** * 递归实现 */ public static ListNode Merge_Recursive(ListNode list1,ListNode list2){ if (list1 == null && list2 == null) { return null; } if (list1 == null) { return list2; } if (list2 == null) { return list1; } ListNode pMergeHead = null; if (list1.val < list2.val) { pMergeHead = list1; pMergeHead.next = Merge(list1.next, list2); } else { pMergeHead = list2; pMergeHead.next = Merge(list1, list2.next); } return pMergeHead; } }