CODEWITHSUNDEEP
javalistmergelinked-listsingly-linked-list
TorusWithSprinkles
TorusWithSprinkles

Reputation: 107

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

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.

Upvotes: 0

Views: 147

Answers (1)

trincot
trincot

Reputation: 350270

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

Upvotes: 1

Related Questions