合并两个链表

题目描述

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

比如以下例子：

题目接口：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {}
};

题目解答：

1.迭代法（尾插法）

这个题目其实我之前做过。只不之前用的是迭代法来做的。迭代法的解题代码如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr){return list2;}if(list2 == nullptr){return list1;}ListNode* head = nullptr;//指向头节点ListNode* tail = nullptr;//指向尾节点while(list1&&list2){if(list1->val<list2->val){if(head == nullptr){head = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;tail->next = nullptr;}else{if(head == nullptr){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;tail->next = nullptr;}}//若list1或者list2里边有未清空的便直接插入if(list1){tail->next = list1;}if(list2){tail->next = list2;}return head;}
};

看起来特别长是吧，是的没错。并且这里还有许多细节要注意。

1.tail表示的是链表的尾节点，所以在尾插了一个节点以后要向后移动来保证tail所在位置依旧是链表尾。

2.tail在插入一个节点以后要在list1或者list2找到下一个节点后置空。

有一说一，迭代法是真的麻烦。

2.递归写法

首先，依照递归法的使用步骤。首先就要先找到重复的子问题。其实非常简单。

1.重复的子问题就是找到两个链表中小的尾插。

2.递归的结束条件，当两个链表有一个空的时候便结束递归，返回不为空的链表。

3.函数体的写法，找到小的插入到链表中。首先便要找到两个链表中比较小的数，然后搞一个新的节点，这个节点的值便是这个小的值。

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr){return list2;}if(list2 == nullptr){return list1;}if(list1->val<list2->val)//确定头节点后一直找剩下的链表的值中较小的尾插{list1->next =  mergeTwoLists(list1->next,list2);return list1;}else{list2->next = mergeTwoLists(list1,list2->next);return list2;}}
};

递归的写法可比迭代的写法简单多了。不过，递归写法的代码不是那么好想出来的。得多多练习才行。