剑指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循环 又是递归，肯定容易出问题，一定要记住，递归函数里面循环体里面又有递归一般就有问题