21.合并两个有序链表

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

示例：

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

代码

1、递归方法

在原有结点基础上建立连接，结果链表的第一个结点从l1、l2的第一个结点选择

 /*递归法*//** * Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode 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;}}
}

2、迭代方法

需要合并成一个新链表，头结点自建，不包含数据，且不输出

/** * Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
/*迭代法*/class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode resHead = new ListNode(-1);//定义合并链表的头结点，输出时需要去除ListNode p = resHead;//操作指针while(l1 != null && l2 != null){if(l1.val <= l2.val){p.next = l1;l1 = l1.next;}else{p.next = l2;l2 = l2.next;}p = p.next;}while(l1 != null){//特例p.next = l1;l1 = l1.next;p = p.next;}while(l2 != null){p.next = l2;l2 = l2.next;p = p.next;}p.next = null;resHead = resHead.next;return resHead;}
}

小结：

递归：重复调用函数自身实现循环称为递归；
迭代：利用变量的原值推出新值称为迭代，或着说迭代是函数内某段代码实现循环；
两者关系：所有的迭代可以转换为递归，但递归不一定可以转换成迭代。

迭代与递归的区别在于：递归是由自己延伸出去的，而迭代是得到新的结果并替代了自己。