本文共 3531 字，大约阅读时间需要 11 分钟。
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
知识点：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
一、非递归解法
1.思路：因为无法得到链表的长度，因此使用while循环判断两个链表的各个节点的值，取较小的值，然后直到有一个链表为空，循环结束，在循环结束时，判断哪个链表为空，则直接在链表的head节点上加上即可
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ head = ListNode(0) #构建一个链表 first = head #赋给first while l1!=None and l2!=None: #如果l1和l2下一个节点都不是None 进行判断 if l1.val <= l2.val: #比较两个单链表的第一个节点 head.next = l1 #值小的的节点作为合并后新链表的第一个节点 l1 = l1.next #值小的节点的下一个节点作为该单链表的新的头节点 else: head.next = l2 l2 = l2.next head = head.next #构建好的链表再赋给head if l1 != None: #l1和l2都会最终指向None head.next = l1 #如果是l2的话，则next为l1 elif l2 != None: head.next = l2 #同理，next为l2 return first.next #最后赋给first
在创建head指针和first指针时，注意先后顺序：是先创建head为0的指针，然后将first指针指向head的节点，然后在合并链表过程中将各个值赋给head的next，最后返回first的next。
做到这里我产生了一个疑问，为什么最后return的是first.next，而不是head呢？
因为head已经到底层去了，而first还保存在头部。经过一系列的操作之后，first会随着head的改变而更新，因为first = head，这里对象是引用操作，而不是赋值操作，与数值类型是不一样的。
二、递归解法
在节点ListNode定义中，定义为节点为结构变量。
节点存储了两个变量：value 和 next。value 是这个节点的值，next 是指向下一节点的指针，当 next 为空指针时，这个节点是链表的最后一个节点。 注意val只代表当前指针的值，比如p->val表示p指针的指向的值；而p->next表示链表下一个节点，也是一个指针。 构造函数包含两个参数 _value 和 _next ，分别用来给节点赋值和指定下一节点# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = None class Solution: def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ if l1==None and l2==None: return None if l1==None: return l2 if l2==None: return l1 if l1.val<=l2.val: #对比两个链表节点的值，如果l1小于l2 l1.next=self.mergeTwoLists(l1.next,l2) #那么则指向l1下一个节点，再与l2作比较 return l1 else: l2.next=self.mergeTwoLists(l1,l2.next) return l2
以下是Java版本：
题目大意：合并两个排序链表并返回一个新的列表。新的链表的结果由原先的两个链表结点组成，也就是不能合并后的链表不能包含新创建的结点。
解题思路：使用头结点root进行辅助操作，创建一个头结点，再使用两个引用指向两个链表的头结点，将较小的结点值的结点摘下来接到root链表的末尾，同时被摘的链头引用移动到下一个结点，一直操作，到到原先两个链表中有一个为空，最后再将剩下的结点接到root链表的末尾。最后返回root的下一个结点，其就为新的链表头。
Java代码：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(0); // 创建一个头结点，最后还要删除掉 ListNode tail = head; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; // 移动到新的尾结点 } tail.next = (l1 != null ? l1 : l2); return head.next; // head的下一个节点是第一个数据结点 }}
转载地址：http://ksuvi.baihongyu.com/