Java

java怎么合并两个有序链表

小亿
140
2023-11-16 09:56:59
栏目: 编程语言

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

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

以下是一个示例的 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;
        }
    }
}

输出结果:

1 1 2 3 4 4

0
看了该问题的人还看了