题目：
链接：https://leetcode.cn/problems/merge-two-sorted-lists/
方式一：
方式二：
代码示例：
package com.zy.leetcode.LeetCode_21;/*** @Author: zy* @Date: 2024-12-26-11:38* @Description: 合并两个有序链表*/
public class ListNode_21 {private int val;private ListNode_21 next;public ListNode_21(int val, ListNode_21 next) {this.val = val;this.next = next;}public ListNode_21() {}public ListNode_21(int val) {this.val = val;}//传入一个数组，初始化链表public static ListNode_21 initListNode(int[] arr) {ListNode_21 dummy = new ListNode_21(0);ListNode_21 cur = dummy;for (int num : arr) {cur.next = new ListNode_21(num);cur = cur.next;}return dummy.next;}//链表打印private void print(ListNode_21 node) {while (node != null) {System.out.print(node.val + " -> ");node = node.next;}}private ListNode_21 mergeList(ListNode_21 p1, ListNode_21 p2) {//哨兵节点ListNode_21 s = new ListNode_21(-1);ListNode_21 p = s;while (p1 != null && p2 != null) {if (p1.val <= p2.val) {p.next = p1;p1 = p1.next;} else {p.next = p2;p2 = p2.next;}p = p.next;}if (p1 != null) {p.next = p1;}if (p2 != null) {p.next = p2;}return s.next;}/*** 优化** @param p1* @param p2* @return*/private ListNode_21 mergeList2(ListNode_21 p1, ListNode_21 p2) {// 特殊情况快速返回if (p1 == null) {return p2;}if (p2 == null) {return p1;}// 哨兵节点，简化操作ListNode_21 dummy = new ListNode_21(-1);ListNode_21 current = dummy;// 合并两个链表while (p1 != null && p2 != null) {if (p1.val <= p2.val) {current.next = p1;p1 = p1.next;} else {current.next = p2;p2 = p2.next;}current = current.next;}// 将剩余部分直接连接current.next = (p1 != null) ? p1 : p2;return dummy.next;}/*** 递归跳用** @param p1* @param p2* @return*/private ListNode_21 mergeList3(ListNode_21 p1, ListNode_21 p2) {// 特殊情况快速返回if (p1 == null) {return p2;}if (p2 == null) {return p1;}if (p1.val <= p2.val) {p1.next = mergeList3(p1.next, p2);return p1;} else {p2.next = mergeList3(p1, p2.next);return p2;}}public static void main(String[] args) {int[] arr1 = {1, 2, 4};int[] arr2 = {1, 3, 4};ListNode_21 p1 = initListNode(arr1);ListNode_21 p2 = initListNode(arr2);ListNode_21 result = new ListNode_21().mergeList(p1, p2);result.print(result);System.out.println("\n--------------------------------");ListNode_21 result2 = new ListNode_21().mergeList2(p1, p2);result2.print(result2);System.out.println("\n------------------------------");ListNode_21 result3 = new ListNode_21().mergeList3(p1, p2);result3.print(result3);}
}
