在Java中合并两个排序的LinkedLists (使用默认的LinkedList类，而不是自定义类)

Question

因此，我正在尝试解决合并两个排序列表的Leetcode问题(#21)，但是我正在尝试使用Java语言中的标准LinkedList类来解决这个问题( Leetcode问题使用了一个自定义的'ListNode‘类。下面是一个使用ListNode类的优雅解决方案：

public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    ListNode head = new ListNode(0);
    ListNode tail = head;
    while(l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    
    if (l1 != null) {
        tail.next = l1;
    } else if (l2 != null) {
        tail.next = l2;
    }
    
    return head.next;
}

这一点我理解得很好，但是如果我使用LinkedList类，我将使用什么来代替l1.val或l2.val？LinkedList似乎没有检索当前节点值的函数，但肯定有办法做到这一点？这似乎是一个非常标准的列表。

Answer 1

LinkedList类不提供对节点的访问，只提供对值的访问。因此，从来没有像l1.val和l1.next这样的属性访问。遍历链表实例的一种方法是使用listIterator方法创建迭代器。这个迭代器不会产生节点，而会产生值。

尽管可以使用LinkedList类接近第一个循环，但是不能执行在最后一个if...else块中完成的步骤:您必须将剩余列表的每个值添加到结果列表--没有办法将结果列表的尾部与另一个列表链接起来。

下面是你如何使用迭代器来做这件事。请注意，我已经将while条件设置为逻辑OR条件，而不是AND条件，因此要处理上面段落中提到的问题：

public LinkedList<Integer> mergeTwoLists(LinkedList<Integer> l1, LinkedList<Integer> l2) {
    LinkedList<Integer> result = new LinkedList<Integer>();
    ListIterator<Integer> iter1 = l1.listIterator();
    ListIterator<Integer> iter2 = l2.listIterator();
    Integer value1 = iter1.hasNext() ? iter1.next() : null;
    Integer value2 = iter2.hasNext() ? iter2.next() : null;
    while (value1 != null || value2 != null) {
        if (value2 == null || value1 != null && value1 <= value2) {
            result.add(value1);
            value1 = iter1.hasNext() ? iter1.next() : null;
        } else {
            result.add(value2);
            value2 = iter2.hasNext() ? iter2.next() : null;
        }
    }
    return result;
}