剑指offer面试题25 ：合并两个有序链表

偏执的太偏执、 2023-02-17 15:52 27阅读 0赞

题目:

> 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。  
>   
> 示例1：  
> 输入：1->2->4, 1->3->4  
> 输出：1->1->2->3->4->4  
> 限制：  
> 0 <= 链表长度 <= 1000

### 一、迭代 ###

思路不用说，选两个链表的头结点中 val 较小的，然后移动相应的链表指针，一直到结束；  
需要注意的是结果用一个 listNode 保存之后，指向结果的这个指针也移动到next，一直到了最后。  
所以最好准备另一个指针指向他，而过程中这个指针不变，返回的时候就能更方便。

/**
    * 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 ans=new ListNode(0);
            ListNode head=ans;
    
            while(l1!=null&&l2!=null){
        
                if(l1.val>l2.val){
        
                    ans.next=l2;//选择小的值
                    ans=ans.next;
                    l2=l2.next;
                }else{
        
                    ans.next=l1;
                    ans=ans.next;
                    l1=l1.next;
                }
                
            }
            if(l1!=null){
        
                ans.next=l1;//补充结果
            }
            if(l2!=null){
        
                ans.next=l2;
            }
            return head.next;
        }
    }

### 二、递归 ###

while 循环用递归替代。

首先选择一个节点，选择之后，将某一条链表的 next 和另一条链表继续进行合并；  
合并的过程里又是选择一个节点，选择之后……

/**
    * 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) {
        
            if(l1==null){
        
                return l2;
            }
            if(l2==null){
        
                return l1;
            }
            if(l1.val<l2.val){
        
                l1.next=mergeTwoLists(l1.next,l2);//l1的next和l2继续递归的做操作，保存了l1的第一个节点
                return l1;
            }else{
        
                l2.next=mergeTwoLists(l1,l2.next);
                return l2;
            }
        }
    }