合并两个有序链表(Java实现)
题目:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
解法一:常规解法
package Day47; /** * @Author Zhongger * @Description 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 * @Date 2020.3.20 */ public class MergeTwoListsSolution { public static void main(String[] args) { ListNode l1_1 = new ListNode(1); ListNode l1_2 = new ListNode(2); ListNode l1_3 = new ListNode(4); l1_1.next=l1_2; l1_2.next=l1_3; ListNode l2_1 = new ListNode(1); ListNode l2_2 = new ListNode(3); ListNode l2_3 = new ListNode(4); l2_1.next=l2_2; l2_2.next=l2_3; MergeTwoListsSolution solution = new MergeTwoListsSolution(); ListNode mergeTwoLists = solution.mergeTwoLists(l1_1, l2_1); ListNode temp=mergeTwoLists; while (temp!=null){ System.out.println(temp); temp=temp.next; } } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1==null&&l2==null){ return null; } ListNode resList=new ListNode(0);//头结点 ListNode temp=resList;//辅助节点 while (l1!=null&&l2!=null){ if (l1.val<l2.val){ temp.next=new ListNode(l1.val); l1=l1.next; }else { temp.next=new ListNode(l2.val); l2=l2.next; } temp=temp.next; } if (l1==null){ temp.next=l2; } if (l2==null){ temp.next=l1; } return resList.next; } } class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; } @Override public String toString() { return val+" "; } }
解法二:递归解法
/** * 递归求解 * @param l1 * @param l2 * @return */ public ListNode mergeTwoLists2(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }
关于递归求解的方法,可以查看该链接。https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/yi-kan-jiu-hui-yi-xie-jiu-fei-xiang-jie-di-gui-by-/