题目
输入俩个递增排序的链表，合并这俩个链表并使新链表中的节点仍然是递增序列。例如下图链表1和链表2，合并后的升序链表为链表3，链表节点定义如下：
typedef int TElemType;//链表节点值的数据类型 struct ListNode { TElemType m_nValue; ListNode* m_pNext; };
分析
我们可以构造出来一个链表。表头不存储数据，定义俩指针p1和p2分别指向链表1和链表2表头。再创建一个记录新的链表尾部的指针previously。然后对比俩指针所指节点的值，谁小取谁的值，然后对应的指针后移。将新的节点连接到previously指向的节点后面，然后更新previously。直到俩个链表有一个为nullptr或者俩个均为nullptr。
当有一个链表为空退出循环时，直接将previously的下一个节点连接到另一个链表指针的节点。若均为nullptr时，不进行任何操作。(但是如果题目要求不允许修改原链表，你就只能继续遍历链表，然后创建新节点，连接。)
下面代码是不允许修改的原链表代码，且未优化
C++
#include <iostream> using namespace std; typedef int TElemType;//链表节点值的数据类型 struct ListNode { TElemType m_nValue; ListNode* m_pNext; }; ListNode* CreateNode(TElemType val)//创建节点 { ListNode* Node = new ListNode(); Node->m_nValue = val; Node->m_pNext = nullptr; return Node; } void connect(ListNode* L1, ListNode* L2)//链接 { L1->m_pNext = L2; } void PrintList(ListNode* head) { while (head != nullptr) { cout << head->m_nValue; if (head->m_pNext != nullptr) { cout << "->"; } else { cout << endl; } head = head->m_pNext; } } ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并俩链表 { if (nullptr == pHead1 && nullptr == pHead2) { return nullptr; } if (nullptr == pHead1) { return pHead2; } if (nullptr == pHead2) { return pHead1; } ListNode* p1 = pHead1; ListNode* p2 = pHead2; ListNode* NewNode = nullptr;//新创建的节点指针 ListNode* head = new ListNode();//新链表的表头指针 head->m_nValue = 0; head->m_pNext = nullptr; ListNode* previously = head;//表尾指针 while (p1 != nullptr && p2 != nullptr) { int min = 0;//用于保存小值的节点 //找最小值 if (p1->m_nValue < p2->m_nValue) { min = p1->m_nValue; p1 = p1->m_pNext; } else { min = p2->m_nValue; p2 = p2->m_pNext; } //创建新节点 NewNode = new ListNode(); NewNode->m_nValue = min; NewNode->m_pNext = nullptr; //连接 previously->m_pNext = NewNode; //更新链表尾指针 previously = NewNode; } /*不可修改原链表的代码*/ while (p1 != nullptr) { int min = p1->m_nValue; p1 = p1->m_pNext; //创建新节点 NewNode = new ListNode(); NewNode->m_nValue = min; NewNode->m_pNext = nullptr; //连接 previously->m_pNext = NewNode; //更新链表尾指针 previously = NewNode; } /*不可修改原链表的代码*/ while (p2 != nullptr) { int min = p2->m_nValue; p2 = p2->m_pNext; //创建新节点 NewNode = new ListNode(); NewNode->m_nValue = min; NewNode->m_pNext = nullptr; //连接 previously->m_pNext = NewNode; //更新链表尾指针 previously = NewNode; } return head->m_pNext; } int main() { /*测试用例1*/ // 1 3 5 7 2 4 6 8 ListNode* Node1 = CreateNode(1); ListNode* Node3 = CreateNode(3); ListNode* Node5 = CreateNode(5); ListNode* Node7 = CreateNode(7); ListNode* Node2 = CreateNode(2); ListNode* Node4 = CreateNode(4); ListNode* Node6 = CreateNode(6); ListNode* Node8 = CreateNode(8); connect(Node1, Node3); connect(Node3, Node5); connect(Node5, Node7); connect(Node2, Node4); connect(Node4, Node6); connect(Node6, Node8); cout << "链表1:"; PrintList(Node1); cout << "链表2:"; PrintList(Node2); ListNode* head = Merge(Node1, Node2); cout << "合并后的链表："; PrintList(head); cout << "--------------------------------------" << endl; /*测试用例2*/ // 1 2 4 3 5 8 Node1 = CreateNode(1); Node2 = CreateNode(2); Node4 = CreateNode(4); Node3 = CreateNode(3); Node5 = CreateNode(5); Node8 = CreateNode(8); connect(Node1, Node2); connect(Node2, Node4); connect(Node3, Node5); connect(Node5, Node8); cout << "链表1:"; PrintList(Node1); cout << "链表2:"; PrintList(Node3); head = Merge(Node1, Node3); cout << "合并后的链表："; PrintList(head); return 0; }
上述代码中发现创建新节点多次重复我们可以封装成一个函数
int min = p2->m_nValue; p2 = p2->m_pNext; //创建新节点 NewNode = new ListNode(); NewNode->m_nValue = min; NewNode->m_pNext = nullptr; //连接 previously->m_pNext = NewNode; //更新链表尾指针 previously = NewNode;
优化后的不允许修改原链表代码
C++
#include <iostream> using namespace std; typedef int TElemType;//链表节点值的数据类型 struct ListNode { TElemType m_nValue; ListNode* m_pNext; }; ListNode* CreateNode(TElemType val)//创建节点 { ListNode* Node = new ListNode(); Node->m_nValue = val; Node->m_pNext = nullptr; return Node; } void connect(ListNode* L1, ListNode* L2)//链接 { L1->m_pNext = L2; } void PrintList(ListNode* head)//输出 { while (head != nullptr) { cout << head->m_nValue; if (head->m_pNext != nullptr) { cout << "->"; } else { cout << endl; } head = head->m_pNext; } } //创建并连接新节点 //此处传参必须要二级指针，因为要修改指针 void connNewNode(ListNode** previously, ListNode** p) { //创建新节点 ListNode* NewNode = new ListNode(); NewNode->m_nValue = (*p)->m_nValue; NewNode->m_pNext = nullptr; //连接 (*previously)->m_pNext = NewNode; //更新新链表尾指针 *previously = NewNode; //更新原链表指针 *p = (*p)->m_pNext; } ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并俩链表 { if (nullptr == pHead1) { return pHead2; } if (nullptr == pHead2) { return pHead1; } ListNode* p1 = pHead1; ListNode* p2 = pHead2; ListNode* head = new ListNode();//新链表的表头指针 head->m_nValue = 0; head->m_pNext = nullptr; ListNode* previously = head;//表尾指针 while (p1 != nullptr && p2 != nullptr) { if (p1->m_nValue < p2->m_nValue) { connNewNode(&previously, &p1); } else { connNewNode(&previously, &p2); } } /*不可修改原链表的代码*/ while (p1 != nullptr) { connNewNode(&previously, &p1); } /*不可修改原链表的代码*/ while (p2 != nullptr) { connNewNode(&previously, &p2); } return head->m_pNext; } int main() { /*测试用例1*/ // 1 3 5 7 2 4 6 8 ListNode* Node1 = CreateNode(1); ListNode* Node3 = CreateNode(3); ListNode* Node5 = CreateNode(5); ListNode* Node7 = CreateNode(7); ListNode* Node2 = CreateNode(2); ListNode* Node4 = CreateNode(4); ListNode* Node6 = CreateNode(6); ListNode* Node8 = CreateNode(8); connect(Node1, Node3); connect(Node3, Node5); connect(Node5, Node7); connect(Node2, Node4); connect(Node4, Node6); connect(Node6, Node8); cout << "链表1:"; PrintList(Node1); cout << "链表2:"; PrintList(Node2); ListNode* head = Merge(Node1, Node2); cout << "合并后的链表："; PrintList(head); cout << "--------------------------------------" << endl; /*测试用例2*/ // 1 2 4 3 5 8 Node1 = CreateNode(1); Node2 = CreateNode(2); Node4 = CreateNode(4); Node3 = CreateNode(3); Node5 = CreateNode(5); Node8 = CreateNode(8); connect(Node1, Node2); connect(Node2, Node4); connect(Node3, Node5); connect(Node5, Node8); cout << "链表1:"; PrintList(Node1); cout << "链表2:"; PrintList(Node3); head = Merge(Node1, Node3); cout << "合并后的链表："; PrintList(head); return 0; }
如果我们可以修改原链表，代码将更加简单。由于只修改了Merge函数，所以展示部分代码
C++
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并俩链表 { if (nullptr == pHead1) { return pHead2; } if (nullptr == pHead2) { return pHead1; } ListNode* p1 = pHead1; ListNode* p2 = pHead2; ListNode* head = new ListNode();//新链表的表头指针 head->m_nValue = 0; head->m_pNext = nullptr; ListNode* previously = head;//表尾指针 while (p1 != nullptr && p2 != nullptr) { if (p1->m_nValue < p2->m_nValue) { connNewNode(&previously, &p1); } else { connNewNode(&previously, &p2); } } /*可修改原链表的代码*/ if (p1 != nullptr) { previously->m_pNext = p1; } /*可修改原链表的代码*/ if (p2 != nullptr) { previously->m_pNext = p2; } return head->m_pNext; }
本章完！
