正文

Java中合并两个单链表：方法、步骤与示例

/0 浏览量
0420

在Java中，合并两个单链表是一个常见的操作，尤其是在处理链表数据结构时。下面，我将详细介绍如何在Java中合并两个单链表，包括方法、步骤和示例代码。

方法概述

合并两个单链表的方法主要有两种：递归和非递归。

1. 递归方法

递归方法利用函数的嵌套调用，将合并问题分解为更小的子问题。这种方法简洁，但可能在链表较长时导致栈溢出。

2. 非递归方法

非递归方法通常使用循环来遍历链表，并逐步合并节点。这种方法在处理大型链表时更为稳定，且不易出现栈溢出问题。

步骤详解

1. 定义单链表节点类

首先，我们需要定义一个单链表的节点类，通常包含两个属性：数据（data）和指向下一个节点的引用（next）。

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

2. 递归合并方法

递归方法的基本思路是：将一个链表的头部节点与另一个链表的头部节点进行比较，将较小的节点连接到合并后的链表的末尾，然后递归地对剩余的链表进行合并。

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;
    }
}

3. 非递归合并方法

非递归方法通常使用一个哑节点（dummy node）作为合并后链表的头部，然后通过循环遍历两个链表，将较小的节点依次连接到哑节点的下一个节点。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    if (l1 != null) {
        current.next = l1;
    } else if (l2 != null) {
        current.next = l2;
    }
    
    return dummy.next;
}

4. 测试合并方法

为了验证合并方法是否正确，我们可以创建两个链表，并使用合并方法将它们合并，然后打印合并后的链表。

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);

    ListNode mergedList = mergeTwoLists(l1, l2);

    while (mergedList != null) {
        System.out.print(mergedList.val + " ");
        mergedList = mergedList.next;
    }
}

运行上述代码，输出结果应为：1 1 2 3 4 4，表示两个链表已经成功合并。

-- 展开阅读全文 --