微信

使用微信服务,更方便

职友集>程序员面试题 > 两个不交叉的有序链表的合并

两个不交叉的有序链表的合并

2014-09-10 06:30:01 阅读( 55 )

473人 收藏本页

标签:程序员面试题

有两个有序链表,各自内部是有序的,但是两个链表之间是无序的。
算法思路:当然是循环逐项比较两个链表了,如果一个到了头,就不比较了,直接加上去。
注意,对于2个元素的Data相等(仅仅是Data相等哦,而不是相同的引用),我们可以把它视作前面的Data大于后面的Data,从而节省了算法逻辑。
static Link MergeTwoLink(Link head1, Link head2)
{
Link head = new Link(null, Int16.MinValue);
Link pre = head;
Link curr = head.Next;
Link curr1 = head1;
Link curr2 = head2;
//compare until one link run to the end
while (curr1.Next != null && curr2.Next != null)
{
if (curr1.Next.Data < curr2.Next.Data)
{
curr = new Link(null, curr1.Next.Data);
curr1 = curr1.Next;
}
else
{
curr = new Link(null, curr2.Next.Data);
curr2 = curr2.Next;
}
pre.Next = curr;
pre = pre.Next;
}
//if head1 run to the end
while (curr1.Next != null)
{
curr = new Link(null, curr1.Next.Data);
curr1 = curr1.Next;
pre.Next = curr;
pre = pre.Next;
}
//if head2 run to the end
while (curr2.Next != null)
{
curr = new Link(null, curr2.Next.Data);
curr2 = curr2.Next;
pre.Next = curr;
pre = pre.Next;
}
return head;
}

如果这两个有序链表交叉组成了Y型呢,比如说:

这时我们需要先找出这个交叉点(图中是11),这个算法参见第9题,我们这里直接使用第10道题目中的方法GetIntersect。
然后局部修改上面的算法,只要其中一个链表到达了交叉点,就直接把另一个链表的剩余元素都加上去。如下所示:
static Link MergeTwoLink2(Link head1, Link head2)
{
Link head = new Link(null, Int16.MinValue);
Link pre = head;
Link curr = head.Next;
Link intersect = GetIntersect(head1, head2);
Link curr1 = head1;
Link curr2 = head2;
//compare until one link run to the intersect
while (curr1.Next != intersect && curr2.Next != intersect)
{
if (curr1.Next.Data < curr2.Next.Data)
{
curr = new Link(null, curr1.Next.Data);
curr1 = curr1.Next;
}
else
{
curr = new Link(null, curr2.Next.Data);
curr2 = curr2.Next;
}
pre.Next = curr;
pre = pre.Next;
}
//if head1 run to the intersect
if (curr1.Next == intersect)
{
while (curr2.Next != null)
{
curr = new Link(null, curr2.Next.Data);
curr2 = curr2.Next;
pre.Next = curr;
pre = pre.Next;
}
}
//if head2 run to the intersect
else if (curr2.Next == intersect)
{
while (curr1.Next != null)
{
curr = new Link(null, curr1.Next.Data);
curr1 = curr1.Next;
pre.Next = curr;
pre = pre.Next;
}
}
return head;
}

来自分智网

下一篇:判断两个单链表是否相交

上一篇:找出单链表的中间元素

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题