MyException - 我的异常网
当前位置:我的异常网» 编程 » 合龙有序链表

合龙有序链表

www.MyException.Cn  网友分享于:2013-03-15  浏览:3次
合并有序链表
合并两个升序链表,要点在于:边界条件判断,即链表可能为空。

剩下的就是依次比较两个链表的头结点,把更小的节点放到新链表中去,继续遍历。算法实现如下:
/*
1: 边界条件判断
2: 头结点的值
3:
*/
Node * mergeOrderedLinkedList(Node *head1, Node *head2)
{
    //边界条件判断
    if(null == head1) return head2;
    if(null == head2) return head1;

    Node *head = null, *p1 = null, *p2 = null;
    //获取头结点
    if(head1->value < head2->value)
    {
        head = head1;
        p1 = head1->next;
        p2 = head2;
    }
    else
    {
        head = head2;
        p2 = head2->next;
        p1 = head1;
    }

    //依次合并
    Node *p3 = head;
    while(null != p1 && null != p2)
    {
        if(p1->value < p2->value)
        {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        }
        else
        {
            p3->next = p2;
            p3  = p2;
            p2  = p2->next;
        }
    }
    if(null == p1)
    {
        p3->next = p2;
    }
    else{
        p3->next = p1;
    }
    return head;
}



(2)递归实现。
按照上面的算法实现,思路很清晰简单,但是代码太长。可以知道每次循环的动作都是相似的,用递归应该可以实现。如下
Node * mergeOrderedLinkedListRecursive(Node *head1, Node *head2)
{
    //边界条件判断
    if(null == head1) return head2;
    if(null == head2) return head1;

    Node *head = null;
    if(head1->value < head2->value)
    {
        head = head1;
        head->next = mergeOrderedLinkedListRecursive(head1->next, head2);
    }
    else
    {
        head = head2;
        head->next = mergeOrderedLinkedListRecursive(head1, head2->next);
    }
    return head;
}


文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有