今天刷第2道LeetCode题，合并两个有序链表：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
1. 先判断边界条件，如果有任意一个链表为空，则直接返回其中不为空的链表
2. 然后在一个循环里面，同时从左往右遍历两个链表
3. 遍历过程中，依次比较两个链表的值，把较小值放入新链表中，然后将对应链表的指针往右移动一位
4. 重复步骤3，直到：遍历次数超出两个链表长度之和，或者任何一个链表已经遍历到了末尾，则跳出循环
5. 把未遍历完的链表的后续数值全部放入新链表中，结束
java实现如下：
public class MergeTwoLists { public static void main(String[] args) { ListNode listNode1 = new ListNode(1); listNode1.next = new ListNode(2); listNode1.next.next = new ListNode(4); ListNode listNode2 = new ListNode(1); listNode2.next = new ListNode(3); listNode2.next.next = new ListNode(4); ListNode listNode = mergeTwoLists(listNode1, listNode2); ListNode.print(listNode); } public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode result = new ListNode(); ListNode resultHead = result; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { result.next = new ListNode(l1.val); l1 = l1.next; } else { result.next = new ListNode(l2.val); l2 = l2.next; } } if (l1 != null) { result.next = l1; } if (l2 != null) { result.next = l2; } return resultHead.next; } } class ListNode { int val; ListNode next; ListNode(int x) { val = x; } ListNode() { } public static void print(ListNode listnode) { while (listnode != null) { System.out.println(listnode.val); listnode = listnode.next; } } }
一开始是这样去实现的，但是发现，输出结果是4，也就是最后的结果，这个链表只有一个节点。其实问题在于最后的输出，是该链表的最后一个节点，链表头的指针丢失了，java没有像c语言那样的指针。
于是我把代码改成以下这样，在函数中加入额外的参数，期待以此来保存结果链表的头指针。然后事与愿违，输出结果还是不变。问题明天再找，先休息。
public class MergeTwoLists { public static void main(String[] args) { ListNode listNode1 = new ListNode(1); listNode1.next = new ListNode(2); listNode1.next.next = new ListNode(4); ListNode listNode2 = new ListNode(1); listNode2.next = new ListNode(3); listNode2.next.next = new ListNode(4); ListNode result = new ListNode(); mergeTwoLists(listNode1, listNode2, result); ListNode.print(result.next); } public static void mergeTwoLists(ListNode l1, ListNode l2, ListNode result) { if (l1 == null) { result.next = l2; } if (l2 == null) { result.next = l1; } while (l1 != null && l2 != null) { if (l1.val <= l2.val) { result.next = new ListNode(l1.val); l1 = l1.next; } else { result.next = new ListNode(l2.val); l2 = l2.next; } } if (l1 != null) { result.next = l1; } if (l2 != null) { result.next = l2; } } } class ListNode { int val; ListNode next; ListNode(int x) { val = x; } ListNode() { } public static void print(ListNode listnode) { while (listnode != null) { System.out.println(listnode.val); listnode = listnode.next; } } }
原文：https://www.cnblogs.com/zhangxuezhi/p/11656732.html