兩個有序的列表合并，合并后的鏈表仍舊保持有序；
L1： 1=>3=>4=>7=>8
L2： 1=>2=>5=>6
合并后的鏈表 p：1=>1=>2=>3=>4=>5=>6=>7=>8;
思路：
1：兩個有序列表都是有序的，所以需要確認下先以哪個鏈表作為新鏈表的起始值，所以需要比較L1和L2的頭節(jié)點值的大??；將頭節(jié)點值小的鏈表賦值給鏈表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,兩者指向同一個內(nèi)存地址
1.png
所以當(dāng)temp.Next給定一個新的值時，P.Head同時也會賦值；
2：然后同時循環(huán)L1和L2：每次取出L1,L2列表中的第一個元素作比較，將較小的元素插入到鏈表p中，并同時刪除L1或L2中的這個元素；因為會刪除鏈表中的節(jié)點，所以一定會有一個鏈表先為Null,然后需要把另一個列表的剩余元素全部追加到新列表中；
復(fù)雜度分析：
1：L1或者L2其中一個為NULL，并不需要去循環(huán)鏈表，所以時間復(fù)雜度為O(1);
2：L1和L2都不為NULL，整個代碼塊只有一個while，所以時間復(fù)雜度為O(n);將兩個鏈表合并成新的鏈表就會產(chǎn)生N個內(nèi)存地址，所以空間復(fù)雜度為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,兩者指向同一個內(nèi)存地址
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;
}
