剑指Offer15 合并两个已排序链表

 1 /*************************************************************************
 2     > File Name: 15_MergeTwoSortList.cpp
 3     > Author: Juntaran
 4     > Mail: JuntaranMail@gmail.com
 5     > Created Time: 2016年08月30日 星期二 15时49分47秒
 6  ************************************************************************/
 7 
 8 #include <stdio.h>
 9 #include <malloc.h>
10 
11 // 链表结构体
12 struct ListNode
13 {
14     int val;
15     struct ListNode* next;
16 };
17 
18 // 构造链表
19 ListNode* createList(int* nums, int length)
20 {
21     struct ListNode* head;
22     struct ListNode* p;
23     struct ListNode* q;
24     head = p = (ListNode*)malloc(sizeof(ListNode));
25     head->val = nums[0];
26     for (int i = 1; i < length; ++i)
27     {
28         q = (ListNode*)malloc(sizeof(ListNode));
29         q->val = nums[i];
30         p->next = q;
31         p = q;
32     }
33     p->next = NULL;
34     return head;
35 }
36 
37 // 顺序输出链表
38 void PrintList(ListNode* head)
39 {
40     if (head == NULL)
41         return;
42     ListNode* temp = head;
43     // printf("PrintList:
");
44     while (temp != NULL)
45     {
46         printf("%d ", temp->val);
47         temp = temp->next;
48     }
49     printf("
");
50 }
51 
52 // 合并两个已排序链表
53 ListNode* MergeTwoSortList(ListNode* p, ListNode* q)
54 {
55     if (!p)
56         return q;
57     if (!q)
58         return p;
59     
60     ListNode* temp1 = (p->val > q->val ? q : p);
61     ListNode* temp2 = (p->val > q->val ? p : q);
62     ListNode* head = (temp1);
63     head->next = MergeTwoSortList(temp1->next, temp2);
64     
65     return head;
66 }
67 
68 int main()
69 {
70     int nums1[] = {1,3,5,7};
71     int nums2[] = {2,4,6,8};
72     ListNode* list1 = createList(nums1, 4);
73     ListNode* list2 = createList(nums2, 4);
74     PrintList(list1);
75     PrintList(list2);
76     list1 = MergeTwoSortList(list1, list2);
77     PrintList(list1);
78     
79     return 0;
80     
81 }