面试题----合并两个有序链表---Java

男娘i 2023-07-17 06:09 112阅读 0赞

## 面试题----合并两个有序链表： ##

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

示例：

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

思想：递归

代码如下：

class Solution {
        
        public ListNode mergeTwoLists(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;
            }
    
        }
    }

思想二：分情况讨论

/**
     * 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;
            }
    
            ListNode cur1 = l1;
            ListNode cur2 = l2;
            ListNode result = null;
            ListNode last = null;
            while(cur1 != null && cur2 != null){
        
                if(cur1.val <= cur2.val){
        
                    if(result == null){
        
                        result = cur1;
                    }else{
        
                        last.next = cur1; 
                    }
                    last = cur1;
                    cur1 = cur1.next;
                }else{
        
                    if(result == null){
        
                        result = cur2;
                    }else{
        
                        last.next = cur2;
                    }
                    last = cur2;
                    cur2 = cur2.next;
                }
            }
            if(cur1 != null){
        
                last.next = cur1;
            }else{
        
                last.next = cur2;
            }
            return result;
        }
    }