JZ014-合并两个排序的链表
共 1189字，需浏览 3分钟
·
2021-04-27 19:43
题目描述
题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
示例：
输入
node1: 1 -> 3 -> 5 -> 7 -> 9
node2: 2 -> 4 -> 6 -> 8 -> 10
输出
result 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
解析思路
链表是由一系列连接在一起的结点构成，其中的每个结点都是一个数据结构。
这道题属于链表题型中等题目，做法很简单 ,大致思路如下：
第一种方法：常规方法，
①创建新的链表头pre，用于存储result链表
②两个链表同时遍历，按照下图所示进行连接链表
③返回pre链表头，此时pre就是合并好的新链表
第二种方法：递归，写递归的代码很简单，最重要的要明白递归函数的功能。可以不必关心递归函数的具体实现。
比如这个ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
函数功能：合并两个单链表，返回两个单链表头结点值小的那个节点。
代码Code
方法一：
方法二：
心得体会
思考为什么他可以写出这么好的代码，把每道题的思路理解后用笔记本记录下来，争取刷到融会贯通，即看见有个题能自动归类到某个方面，这样有一定好处。面试最重要的是让面试官日后能愿意与你以后一起工作，因此沟通交流非常重要。比如有时候面试需要交流，看着像是一道排序的题做不出来，就可以跟面试官交流：“我有几个不成熟的想法，一排序，二动态规划，三是直接搜索算法”，面试官可能就给个提示：“你先用排序试试吧“。
end
往期推荐