Merge Two Sorted LinkedLists in Java (using the default LinkedList class, not custom class)

Question

So I'm trying to solve the Leetcode problem (#21) of merging two sorted lists, however I'm trying to do it using the standard LinkedList class in Java (the Leetcode problem uses a custom 'ListNode' class. Here's an elegant solution using the ListNode class:

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

Which I understand just fine, however if I'm using the LinkedList class, what would I use in place of l1.val or l2.val? It seems LinkedList doesn't have a function for retrieving the current node value, but surely there's a way to do this? It seems like it would be very standard for a List.

l1.get(0)?

Turing85
– Turing85

2021-11-20 17:20:23 +00:00
Commented Nov 20, 2021 at 17:20 — Turing85
– Turing85, Commented Nov 20, 2021 at 17:20

trincot · Accepted Answer · 2021-11-20 17:48:58Z

The LinkedList class does not give you access to nodes, just to values. So there is never a property access like l1.val, nor l1.next. One way to traverse a linked list instance, is to create an iterator using the listIterator method. This iterator does not yield nodes, but values.

Although the first loop can be closely approached using the LinkedList class, one cannot do the step that is done in your last if...else block: you'll have to add each value of the remaining list to the result list -- there is no way to link the tail of the result list with another list.

Here is how you could do it with iterators. Note that I have made the while condition a logical OR condition instead of an AND condition, so to deal with the issue mentioned in the above paragraph:

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

Collectives™ on Stack Overflow

Merge Two Sorted LinkedLists in Java (using the default LinkedList class, not custom class)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related