JZ-C-17

剑指offer第十七题:合并两个排序的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//============================================================================
// Name        : JZ-C-17.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description :合并两个排序的链表
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include "List.h"
using namespace std;
ListNode* Merge(ListNode* pHead, ListNode* qHead) {
    if (pHead == NULL) { //考虑某链表为空的情况
        return qHead;
    } else if (qHead == NULL) {
        return pHead;
    }
    ListNode* NewHead = NULL;
    if (pHead->m_nValue < qHead->m_nValue) {
        NewHead = pHead;
        NewHead->m_pNext = Merge(pHead->m_pNext, qHead); //递归
    } else { //包含了相等的情况
        NewHead = qHead;
        NewHead->m_pNext = Merge(pHead, qHead->m_pNext);
    }
    return NewHead;
}
 
// ====================测试代码====================
ListNode* Test(char* testName, ListNode* pHead1, ListNode* pHead2) {
    if (testName != NULL)
        printf("%s begins:\n", testName);
 
    printf("The first list is:\n");
    PrintList(pHead1);
 
    printf("The second list is:\n");
    PrintList(pHead2);
 
    printf("The merged list is:\n");
    ListNode* pMergedHead = Merge(pHead1, pHead2);
    PrintList(pMergedHead);
 
    printf("\n\n");
 
    return pMergedHead;
}
 
// list1: 1->3->5
// list2: 2->4->6
void Test1() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode5 = CreateListNode(5);
 
    ConnectListNodes(pNode1, pNode3);
    ConnectListNodes(pNode3, pNode5);
 
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode6 = CreateListNode(6);
 
    ConnectListNodes(pNode2, pNode4);
    ConnectListNodes(pNode4, pNode6);
 
    ListNode* pMergedHead = Test("Test1", pNode1, pNode2);
 
    DestroyList(pMergedHead);
}
 
// 两个链表中有重复的数字
// list1: 1->3->5
// list2: 1->3->5
void Test2() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode5 = CreateListNode(5);
 
    ConnectListNodes(pNode1, pNode3);
    ConnectListNodes(pNode3, pNode5);
 
    ListNode* pNode2 = CreateListNode(1);
    ListNode* pNode4 = CreateListNode(3);
    ListNode* pNode6 = CreateListNode(5);
 
    ConnectListNodes(pNode2, pNode4);
    ConnectListNodes(pNode4, pNode6);
 
    ListNode* pMergedHead = Test("Test2", pNode1, pNode2);
 
    DestroyList(pMergedHead);
}
 
// 两个链表都只有一个数字
// list1: 1
// list2: 2
void Test3() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
 
    ListNode* pMergedHead = Test("Test3", pNode1, pNode2);
 
    DestroyList(pMergedHead);
}
 
// 一个链表为空链表
// list1: 1->3->5
// list2: 空链表
void Test4() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode5 = CreateListNode(5);
 
    ConnectListNodes(pNode1, pNode3);
    ConnectListNodes(pNode3, pNode5);
 
    ListNode* pMergedHead = Test("Test4", pNode1, NULL);
 
    DestroyList(pMergedHead);
}
 
// 两个链表都为空链表
// list1: 空链表
// list2: 空链表
void Test5() {
    ListNode* pMergedHead = Test("Test5", NULL, NULL);
}
 
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注