从零开始算法之路 ----合并两个有序链表

93 阅读 0 评论 62 点赞

我是靠谱客的博主贪玩香氛，最近开发中收集的这篇文章主要介绍从零开始算法之路 ----合并两个有序链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言：小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）

题源：leetcode（https://leetcode-cn.com/problems/merge-two-sorted-lists/）

题目描述：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解决方案：递归套路

//合并两个有序链表
ListNode* Solution::mergeTwoLists(ListNode *l1, ListNode *l2){
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
} else{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}

完整代码：

#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
//用参数初始化表对数据成员初始化
ListNode(int x=0) : val(x), next(NULL) {}
};
class Solution {
ListNode *first;
public:
Solution(){
first = new ListNode;
}
//去重函数
ListNode* deleteDuplicates(ListNode* head) ;
//输入函数
void input();
//输出 链表函数
void output();
//获得头节点
ListNode* getHead(){
return first;
}
//合并两个有序链表
ListNode * mergeTwoLists(ListNode *L1, ListNode *L2);
};
//输入函数 初始化链表
void Solution::input(){
ListNode *pre,
*newNode;
pre = first;
int
val;
printf("请逐个输入链表:");
while(scanf("%d", &val)){
// 如果val 等于100 输入结束（100 为约定的结束标准）
if(val == 100) break;
//初始化新节点
newNode = new ListNode(val);
// 把新节点连接着当前节点 pre 之后
pre->next = newNode;
// 把新节点变为当前节点
pre = newNode;
}
}
// 输出链表函数
void Solution::output(){
ListNode *current = first->next;
while(current != NULL){
printf("%d ", current->val);
current = current->next;
}
printf("n输出链表结束!");
}
//去重函数
ListNode* Solution::deleteDuplicates(ListNode *head){
//如果链表为空或者只有一个有元素链表肯定不会重复
//	if(head == NULL || head->next == NULL)
//
return head;
//	head->next = deleteDuplicates(head->next);
//	if(head->val == head->next->val) head = head->next;
//	return head;
//
if(head == NULL || head->val != head->val)
//
return head;
//当链表为空或者只有一个元素的时候自然是不会重复的
if(head == NULL || head->next == NULL)
return head;
//思路：1.定义两个变量（first,second）,first指向第一个节点，second 指向第二个节点，
//
2.比较first指向节点的值和second指向节点的值，
//
3.如果这两个值相等（如果不相等，使first指向该节点，重复2），则second指向下一个节点，
//
直到找到和first指向节点不相等的节点，使first指向该节点，重复上述步骤2、3，直到
//
链表最后一个节点
//定义两个变量（first,second）,first指向第一个节点，second 指向第二个节点，
ListNode *first, *second;
first = head;
second = first->next;
// first 指向的节点不为空
while(first != NULL){
// second 指向的节点不为空并且 first指向节点的值和second指向节点的值
while(second!= NULL && first->val == second->val){
//如果这两个值相等，则second指向下一个节点
second = second->next;
}
//使first指向的下一个节点指向second指向的节点
first->next = second;
// 使first指向的节点指向 second指向的节点
first = second;
}
return head;
}
//合并两个有序链表
ListNode* Solution::mergeTwoLists(ListNode *l1, ListNode *l2){
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
} else{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
int main(){
Solution s1,s2;
s1.input();
s2.input();
s1.mergeTwoLists(s1.getHead(), s2.getHead());
s1.output();
return 0;
}