使用Java内置LinkedList实现LeetCode21合并两个有序链表

核心思路 #

Java的LinkedList自带的头部/尾部操作方法完全可以替代自定义ListNode的指针逻辑：

• 原逻辑里的val就是LinkedList中存储的元素本身，直接通过getFirst()就能获取当前待比较的"节点值"
• 原逻辑的tempNode可以用一个新的空LinkedList代替，作为最终的合并结果容器
• currentNode的移动逻辑，对应直接往结果链表的尾部添加元素（addLast()），同时移除原链表的头部元素（相当于指针后移）

实现代码（修改原链表版本，效率更高） #

假设你已经有两个升序排列的LinkedList：list1和list2

import java.util.LinkedList;

public class MergeTwoSortedLists {
    public static void main(String[] args) {
        // 示例输入：已排序的两个链表
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(1);
        list1.add(3);
        list1.add(5);
        
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(2);
        list2.add(4);
        list2.add(6);
        
        LinkedList<Integer> mergedList = mergeTwoLists(list1, list2);
        System.out.println(mergedList); // 输出 [1,2,3,4,5,6]
    }

    public static LinkedList<Integer> mergeTwoLists(LinkedList<Integer> list1, LinkedList<Integer> list2) {
        LinkedList<Integer> mergedList = new LinkedList<>();
        
        // 双指针逻辑：每次取两个链表头部较小的元素
        while (!list1.isEmpty() && !list2.isEmpty()) {
            if (list1.getFirst() <= list2.getFirst()) {
                mergedList.addLast(list1.removeFirst());
            } else {
                mergedList.addLast(list2.removeFirst());
            }
        }
        
        // 处理剩余元素：其中一个链表为空后，直接把另一个链表的剩余元素全部追加
        mergedList.addAll(list1);
        mergedList.addAll(list2);
        
        return mergedList;
    }
}

实现代码（不修改原链表版本） #

如果需要保留原链表的结构，不用removeFirst()，改用索引指针遍历：

import java.util.LinkedList;

public class MergeTwoSortedLists {
    public static void main(String[] args) {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(1);
        list1.add(3);
        list1.add(5);
        
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(2);
        list2.add(4);
        list2.add(6);
        
        LinkedList<Integer> mergedList = mergeTwoLists(list1, list2);
        System.out.println(mergedList); // 输出 [1,2,3,4,5,6]
    }

    public static LinkedList<Integer> mergeTwoLists(LinkedList<Integer> list1, LinkedList<Integer> list2) {
        LinkedList<Integer> mergedList = new LinkedList<>();
        int i = 0, j = 0;
        
        while (i < list1.size() && j < list2.size()) {
            int val1 = list1.get(i);
            int val2 = list2.get(j);
            if (val1 <= val2) {
                mergedList.add(val1);
                i++;
            } else {
                mergedList.add(val2);
                j++;
            }
        }
        
        // 追加剩余元素
        while (i < list1.size()) {
            mergedList.add(list1.get(i));
            i++;
        }
        while (j < list2.size()) {
            mergedList.add(list2.get(j));
            j++;
        }
        
        return mergedList;
    }
}

对应原自定义ListNode逻辑的说明 #

• mergedList 对应原逻辑里的dummyNode（临时头节点），用来存储最终合并结果
• list1.getFirst()/list2.getFirst() 对应原ListNode.val，获取当前节点的值
• removeFirst() 对应原current = current.next，把链表的"指针"移到下一个元素
• addLast() 对应原current.next = new ListNode(val); current = current.next，把新元素接到结果链表的尾部

内容的提问来源于stack exchange，提问作者user21386103