输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
法1:递归
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1 == null) return list2; if(list2 == null) return list1; if(list1.val>= list2.val){ list2.next = Merge(list1, list2.next); return list2; }else{ list1.next = Merge(list1.next, list2); return list1; } } }
做了这么多题,总结出一个规律,要用好递归,只需要做到两个步骤,明确递归的功能和返回值、设置好递归的结束条件,然后把函数当成黑箱,不要被绕进去
法2:创建一个新链表,遍历两个链表,把最小值放进新链表
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { ListNode head = new ListNode(1); ListNode temp = head; while(list1 != null && list2 != null){ if(list1.val>= list2.val){ temp.next = list2; list2 = list2.next; }else{ temp.next = list1; list1 = list1.next; } temp = temp.next; } if(list1 == null) temp.next = list2; if(list2 == null) temp.next = list1; return head.next; } }
原文:https://www.cnblogs.com/tendermelon/p/13028864.html