java怎么合并两个有序链表

55次阅读

共计 933 个字符，预计需要花费 3 分钟才能阅读完成。

可以使用递归的方式来合并两个有序链表。具体步骤如下：

判断两个链表中是否存在为空的情况，若其中一个链表为空，则直接返回另一个链表。
比较两个链表头结点的值，将值较小的头结点作为合并后的链表的头结点。
将较小头结点的 next 指针指向递归调用合并后的链表。
返回合并后的链表的头结点。

以下是一个示例的 Java 代码实现：

class ListNode {int val;
    ListNode next;
    
    ListNode(int val) {this.val = val;
    }
}

public 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);
            return l1;
        } else {l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

使用示例：

public class Main {public static void main(String[] args) {// 创建两个有序链表 
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        
        // 合并两个有序链表 
        Solution solution = new Solution();
        ListNode mergedList = solution.mergeTwoLists(l1, l2);
        
        // 打印合并后的链表 
        while (mergedList != null) {System.out.print(mergedList.val + " ");
            mergedList = mergedList.next;
        }
    }
}