题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图3.7中的链表1和链表2,则合并之后的升序链表如链表3所示。
1.剑指offer书中的代码(递归)
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
if (l1 == null) return l2;
else if (l2 == null) return l1;
ListNode pMergedHead = null;
if (l1.val < l2.val)
{
pMergedHead = l1;
pMergedHead.next = MergeTwoLists(l1.next, l2);
}
else
{
pMergedHead = l2;
pMergedHead.next = MergeTwoLists(l1, l2.next);
}
return pMergedHead;
}
(a)链表1 的头结点的值小于链表2 的头结点的值,因此链表1的头结点是合并后链表的头结点。(b)在剩余的结点中,链表2 的头结点的值小于链表1的头结点的值,因此链表2的头结点是剩余结点的头结点,把这个结点和之前已经合并好的链表的尾结点链接起来。
2.自己先写的(循环感脚也挺好的,就是代码有点长)
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode newHead = null;
if (l1.val > l2.val)
{
newHead = l2;
l2 = l2.next;
}
else
{
newHead = l1;
l1 = l1.next;
}
var tempHead = newHead;
while (l1!=null && l2!=null)
{
if (l1.val > l2.val)
{
tempHead.next = l2;
l2 = l2.next;
}
else
{
tempHead.next = l1;
l1 = l1.next;
}
tempHead = tempHead.next;
}
if (l1 != null)
tempHead.next = l1;
if (l2 != null)
tempHead.next = l2;
return newHead;
}
链表
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int x)
{
val = x;
}
}
网友评论