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
