两个有序的列表合并，合并后的链表仍旧保持有序；
L1： 1=>3=>4=>7=>8
L2： 1=>2=>5=>6
合并后的链表 p：1=>1=>2=>3=>4=>5=>6=>7=>8;
思路：
1：两个有序列表都是有序的，所以需要确认下先以哪个链表作为新链表的起始值，所以需要比较L1和L2的头节点值的大小；将头节点值小的链表赋值给链表p；
if (l1 == null) return l2;
if (l2 == null) return l1;
Node<int> temp1 = l1.Head;
Node<int> temp2 = l2.Head;
LinkedList<int> p = null;//定义新的链表
if (l1.Head.Data <= l2.Head.Data)//给新的链表赋值
{
p = l1;
temp1 = temp1.Next;
}
else
{
p = l2;
temp2 = temp2.Next;
}
Node<int> temp = p.Head;//p.Head赋值给temp,两者指向同一个内存地址
1.png
所以当temp.Next给定一个新的值时，P.Head同时也会赋值；
2：然后同时循环L1和L2：每次取出L1,L2列表中的第一个元素作比较，将较小的元素插入到链表p中，并同时删除L1或L2中的这个元素；因为会删除链表中的节点，所以一定会有一个链表先为Null,然后需要把另一个列表的剩余元素全部追加到新列表中；
复杂度分析：
1：L1或者L2其中一个为NULL，并不需要去循环链表，所以时间复杂度为O(1);
2：L1和L2都不为NULL，整个代码块只有一个while，所以时间复杂度为O(n);将两个链表合并成新的链表就会产生N个内存地址，所以空间复杂度为O(n);
public LinkedList<int> MergeList(LinkedList<int> l1, LinkedList<int> l2)
{
if (l1 == null) return l2;
if (l2 == null) return l1;
Node<int> temp1 = l1.Head;
Node<int> temp2 = l2.Head;
LinkedList<int> p = null;//定义新的链表
if (l1.Head.Data <= l2.Head.Data)//给新的链表赋值
{
p = l1;
temp1 = temp1.Next;
}
else
{
p = l2;
temp2 = temp2.Next;
}
Node<int> temp = p.Head;//p.Head赋值给temp,两者指向同一个内存地址
while (temp1 != null && temp2 != null)
{
if (temp1.Data <= temp2.Data)
{
temp.Next = temp1;
temp1 = temp1.Next;
}
else
{
temp.Next = temp2;
temp2 = temp2.Next;
}
temp = temp.Next;
}
if (temp1 != null)
{
temp.Next = temp1;
}
else if (temp2 != null)
{
temp.Next = temp2;
}
return p;
}
