leetcode题解之合并两个有序链表

叁歲伎倆 2022-05-15 01:52 115阅读 0赞

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

**示例：**

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

1.非递归法

非递归法较为简单，与合并两个有序数组类似

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           ListNode listNode = new ListNode(0);//前驱节点
             ListNode res = listNode;       
             while (l1 != null && l2 != null) {
                  if(l1.val <= l2.val){
                      listNode.next = l1;
                      l1 = l1.next;
                       
                  } else{
                      listNode.next = l2;
                      l2 = l2.next;
                  }
                 listNode = listNode.next;
             }
            while (l1 !=null){
              listNode.next = l1;
                l1 = l1.next;
                listNode = listNode.next;          
             }
             while (l2 !=null){
                listNode.next = l2;
                l2 = l2.next;
                listNode = listNode.next;
                 
             }
            return res.next;//listNode为head的前一个节点，故返回下一个节点
         
        }
    }

2.递归法

//递归法
          public ListNode mergeTwoLists2(ListNode l1, ListNode l2) { 
          //递归出口
             if (l1 == null)
        		  return l2;
        	  if (l2 == null)
        		  return l1;
        	   ListNode head;
        	   if (l1.val <= l2.val) {
        		   head = l1;
        		   head.next = mergeTwoLists1(l1.next, l2);
        	   } else {
        		   head = l2;
        		   head.next = mergeTwoLists1(l1, l2.next);
        	   }
        	   return head;
          }