document.write('分别用指针head1，head2来遍历两个链表，如果当前head1指向的数据小于head2指向的数据，则将
head1指向的结点归入合并后的链表中，否则，将head2指向的结点归入合并后的链表中。如果有一个
链表遍历结束，则把未结束的链表连接到合并后的链表尾部。
下图以一个简单的示例为例介绍合并的具体方法：
由于链表按升序排列，首先通过比较链表第一个结点中元素的大小来确定最终合并后链表的头结点；
接下来每次都找两个链表中剩余结点的最小值链接到被合并的链表后面，如上图中的虚线所示。具体实
现代码如下：
class LNode:
def __new__(self,x):
self.data=x
self.next=None
# 方法功能:构造链表
def ConstructList(start):
i=start
head=LNode()
head.next=None
tmp=None
cur=head
while i＜7:
tmp=LNode()
tmp.data=i
tmp.next=None
cur.next=tmp
cur=tmp
i+=2
return head
def PrintList(head):
cur=head.next
while cur!=None:
print cur.data,
cur=cur.next
"""
方法功能: 合并两个升序排列的单链表
输入参数: head1与head2代表两个单链表
返回值: 合并后链表的头结点
"""
def Merge(head1,head2):
if head1==None or head1.next==None:
return head2
if head2==None or head2.next==None:
return head1
cur1=head1.next# 用来遍历head1
cur2=head2.next# 用来遍历head2
head=None #合并后链表的头结点
cur=None# 合并后的链表在尾结点
# 合并后链表的头结点为第一个结点元素最小的那个链表的头结点
if cur1.data＞cur2.data:
head=head2
cur=cur2
cur2=cur2.next
else:
head=head1
cur=cur1
cur1=cur1.next
# 每次找链表剩余结点的最小值对应的结点连接到合并后链表的尾部
while cur1!=None and cur2!=None:
if cur1.data＜cur2.data:
cur.next=cur1
cur=cur1
cur1=cur1.next
else:
cur.next=cur2
cur=cur2
cur2=cur2.next
# 当遍历完一个链表后把另外一个链表剩余的结点链接到合并后的链表后面
if cur1!=None:
cur.next=cur1
if cur2!=None:
cur.next=cur2
return head
if __name__=="__main__":
head1=ConstructList(1)
head2=ConstructList(2)
print "head1:",
PrintList(head1)
print "\\nhead2:",
PrintList(head2)
print "\\n合并后的链表:",
head=Merge(head1,head2)
PrintList(head)
程序的运行结果为：
head1: 1 3 5
head2: 2 4 6
合并后的链表：1 2 3 4 5 6
算法性能分析：
以上这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量
来保存结点的地址信息，因此，空间复杂度为O(1)。
');
![\"360截图20190815223804284.jpg\"](\"http://www.alatiku.com/d/file/shiti/291801697bd25385b1b726da0357b393.jpg\")