题目:

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

方法一

遍历

  1. public class Solution {
  2. public ListNode Merge(ListNode list1,ListNode list2) {
  3. ListNode h = new ListNode(-1);
  4. ListNode cur = h;
  5. while(list1 != null && list2 !=null){
  6. if(list1.val<=list2.val){
  7. cur.next = list1;
  8. list1 = list1.next;
  9. }else{
  10. cur.next = list2;
  11. list2 = list2.next;
  12. }
  13. cur = cur.next;
  14. }
  15. if(list1!=null) cur.next = list1;
  16. if(list2!=null) cur.next = list2;
  17. return h.next;
  18. }
  19. }

方法二

递归

  1. //递归
  2. public ListNode Merge1(ListNode list1, ListNode list2) {
  3. if (list1 == null) {
  4. return list2;
  5. } else if (list2 == null) {
  6. return list1;
  7. }else{
  8. if(list1.val<list2.val){
  9. list1.next=Merge1(list1.next, list2);
  10. return list1;
  11. }else {
  12. list2.next=Merge1(list1, list2.next);
  13. return list2;
  14. }
  15. }
  16. }