剑指Offer - 面试题25：合并俩个排序的链表

typedef int TElemType;//链表节点值的数据类型
struct ListNode
{
TElemType m_nValue;
ListNode* m_pNext;
};

分析

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;
}
{
{
{
cout << "->";
}
else
{
cout << endl;
}
}
}
{
{
return nullptr;
}
{
}
{
}
ListNode* NewNode = nullptr;//新创建的节点指针
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;
}
}
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);
cout << "合并后的链表：";
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);
cout << "合并后的链表：";
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;
}
{
{
{
cout << "->";
}
else
{
cout << endl;
}
}
}
//创建并连接新节点
//此处传参必须要二级指针，因为要修改指针
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;
}
{
{
}
{
}
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);
}
}
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);
cout << "合并后的链表：";
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);
cout << "合并后的链表：";
return 0;
}

C++

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并俩链表
{
{
}
{
}
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;
}
}

|
9天前
|

11 0
|
2月前
|

【模拟面试问答】深入解析力扣164题：最大间距（桶排序与排序方法详解）
【模拟面试问答】深入解析力扣164题：最大间距（桶排序与排序方法详解）
16 2
|
2月前
|

19 2
|
2月前
23.合并K个升序链表
23.合并K个升序链表
13 0
|
2月前
|

19 0
|
2月前
|

LeetCode 83题：删除排序链表中的重复元素【面试】
LeetCode 83题：删除排序链表中的重复元素【面试】
13 0
|
2月前
|

LeetCode 题目 82：删除排序链表中的重复元素 II
LeetCode 题目 82：删除排序链表中的重复元素 II
17 0
|
2月前
|

LeetCode 题目 80：删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80：删除排序数组中的重复项 II【算法面试高频题】
26 0
|
2月前
|

Leetcode二十三题：合并K个升序链表【22/1000 python】
Leetcode二十三题：合并K个升序链表【22/1000 python】
18 0
|
3月前
|

【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
25 0