劍指offer之合并已排序鏈表（遞歸實現(xiàn)）

1 問題

合并2個已經(jīng)排好序的鏈接，比如

1->3->5->7

2->4->6

合并后新的鏈表如下

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

 
2 代碼實現(xiàn)

    #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 運(yùn)行結(jié)果

    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 總結(jié)

我一開始寫成這樣了

    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循環(huán) 又是遞歸，肯定容易出問題，一定要記住，遞歸函數(shù)里面循環(huán)體里面又有遞歸一般就有問題
 

 


 


作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)