剑指offer之合并已排序链表（递归实现）

1 问题

合并2个已经排好序的链接，比如

1->3->5->7

2->4->6

合并后新的链表如下

1->2->3->4->5->6->7

 
2 代码实现

    #include <stdio.h>
    typedef struct Node
    {
        int val;
        struct Node *next;
    } Node;
     
    /*
     *print list
     */
    void print_list(Node *head)
    {
        if (head == NULL)
        {
            printf("head is NULL\n");
            return;
        }
        Node *p = head;
        while (p != NULL)
        {
            printf("value is %d\n", p->val);
            p = p->next;
        }
    }
     
     
    /*
     *合并链表
     */
    struct Node* merge(Node *head1, Node *head2)
    {
        if (head1 == NULL)
        {
            return head2;
        }
        if (head2 == NULL)
        {
            return head1;
        }
        struct Node *new = NULL;
        if (head1->val < head2->val)
        {
            new = head1;
            new->next = merge(head1->next, head2);
        }
        else
        {
            new = head2;
            new->next = merge(head1, head2->next);
        }
        return new;
    }
     
     
    int main()
    {
        
        //list1 0->3->5->9;
        Node head, node1, node2, node3;
        head.val = 0;
        head.next = &node1;
        node1.val = 3;
        node1.next = &node2;
        node2.val = 5;
        node2.next = &node3;
        node3.val = 9;
        node3.next = NULL;
        printf("list1 is such as\n");
        print_list(&head);
        //list2 1->4->6
        Node head1, node4, node5;
        head1.val = 1;
        head1.next = &node4;
        node4.val = 4;
        node4.next = &node5;
        node5.val = 6;
        node5.next = NULL;
        printf("list2 is such as\n");
        print_list(&head1);
        printf("merge list1 and list2\n");
        Node *new = merge(&head, &head1);
        print_list(new);
        return 0;
    }

 
3 运行结果

    list1 is such as
    value is 0
    value is 3
    value is 5
    value is 9
    list2 is such as
    value is 1
    value is 4
    value is 6
    merge list1 and list2
    value is 0
    value is 1
    value is 3
    value is 4
    value is 5
    value is 6
    value is 9


4 总结

我一开始写成这样了

    struct Node* merge(Node *head1, Node *head2)
    {
        if (head1 == NULL)
        {
            return head2;
        }
        if (head2 == NULL)
        {
            return head1;
        }
        struct Node *new = NULL;
        while (head1 != NULL && head2 != NULL)
        {
            if (head1->val < head2->val)
            {
                new = head1;
                new->next = merge(head1->next, head2);
            }
            else
            {
                new = head2;
                new->next = merge(head1, head2->next);
            }
        }
        return new;
    }

加了while循环 又是递归，肯定容易出问题，一定要记住，递归函数里面循环体里面又有递归一般就有问题
 

 


 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)