链表合并
链表合并
https://www.nowcoder.com/practice/46bda7f0570a47b6b54a29a0a6ae4c27?tpId=98&tqId=32879&tPage=3&rp=3&ru=/ta/2019test&qru=/ta/2019test/question-ranking
题目难度：二星
考察点：链表合并
方法：链表
1.分析：
其实这个题就是合并两个有序链表，如果按照作弊的方法呢，就可以不把这个东西当作链表，直接把这个东西当作数组，即直接把两个有序数组进行排序，就跟之前说过的归并排序差不多，类似代码如下：
int a[15],b[15],c[15];
void Merge_Sort(int n, int m)///n是数组a的长度，m是数组b的长度
{
int i, j, k;
i = j = k = 0;
while(i<n && j<m)
{
if(a[i] < b[j])///因为是已经排好序的只要a[i]比b[j]小i就后移
c[k++] = a[i++];
else///同理
c[k++] = b[j++];
}
while(i < n)///这个是b数组已经全部比完
c[k++] = a[i++];
while(j < m)///这个是a数组已经全部比完
c[k++] = b[j++];
} 那么如果这个题目采用链表的方式的话，其实跟上述的方法差不多，也是一个个比较，但是有所不同的是通过链表的方式进行比较，首先就是写一个创建一个新链表的函数，然后在写一个合并链表的函数。创建链表就可以用我们处理过输入之后的vector当作链表的输入，然后创建一个头节点，即 ListNode *head = new ListNode;然后在创建一个当前节点now=head用来遍历，在创建一个临时节点用来当作now->next，最后返回head就可以了，链表的合并时最基础的东西，这个具体的实现方式还是直接看代码把。 算法实现：
(1). getline,处理输入。 (2). 创建链表。
(3). 合并链表。
(4). 将合并之后的有序链表进行输出
2.复杂度分析：
时间复杂度：O(n)空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
struct ListNode{
int val;
ListNode *next;
};
ListNode* creatList(string s){
stringstream ss(s);
vector<int> a;
int x;
while(ss >> x) a.push_back(x);
ListNode *head = new ListNode;
head->val = a[0];
ListNode* now = head;
for(int i=1; i<a.size(); i++){
ListNode *tmp = new ListNode;
tmp->val = a[i];
tmp->next = nullptr;
now->next = tmp;
now = now->next;
}
return head;
}
ListNode* mergeList(ListNode* h1, ListNode* h2){
if(h1 == nullptr) return h2;
if(h2 == nullptr) return h1;
ListNode *head = new ListNode;
ListNode *now = head;
while(h1 && h2) {
int x;
if(h1->val < h2->val) {
x = h1->val;
h1 = h1->next;
}
else {
x = h2->val;
h2 = h2->next;
}
ListNode *tmp = new ListNode;
tmp->val = x;
tmp->next = nullptr;
now->next = tmp;
now = now->next;
}
if(h1) now->next = h1;
else now->next = h2;
return head;
}
int main(){
ListNode *h1, *h2;
string s1, s2;
getline(cin, s1);
getline(cin, s2);
h1 = creatList(s1);
h2 = creatList(s2);
ListNode *p = mergeList(h1, h2);
p = p->next;
while(p){
cout<<p->val<<" ";
p = p->next;
}
return 0;
}
CVTE公司福利 258人发布
投递百度等公司10个岗位 >