LeetCode刷题系列 -- 21. 合并两个有序链表

题目：

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

 

示例：

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists  

思路1：

  1、 定义一个空节点 beforeHead 表示 拼接后的头结点的前一个节点，currentNode 表示当前节点

 2、一次遍历两个有序的链表，将当前比较小的链表值拿出来，拼接到当前节点 currentNode的后面

3、将currentNode 往后移动一位，拿出节点的原链表往后移动一位

 

Java代码如下：

/** * 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 beforeHead = new ListNode(0); ListNode currentNode = beforeHead; while (true){ if(l1==null&&l2==null){ break; } if(l1!=null&&l2!=null) { if (l1.val < l2.val) { currentNode.next = l1; currentNode = currentNode.next; l1 = l1.next; }else { currentNode.next = l2; currentNode = currentNode.next; l2 = l2.next; } }else { while (l1!=null){ currentNode.next = l1; currentNode = currentNode.next; l1 = l1.next; } while (l2!=null){ currentNode.next = l2; currentNode = currentNode.next; l2 = l2.next; } } } return beforeHead.next; } }

 思路2，利用递归方法

Java代码如下：

/** * 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 list1,ListNode list2){ if(list1 == null){ return list2; } if(list2 == null){ return list1; } if(list1.val<=list2.val){ list1.next = mergeTwoLists(list1.next,list2); return list1; }else { list2.next = mergeTwoLists(list1,list2.next); return list2; } } }