ShorterLinkedListMergeInPlace.java

// https://stackoverflow.com/questions/57447358/does-this-merge-function-of-mergesort-take-o-1-space-or-on-space/57448761?noredirect=1#comment101376213_57448761
public final class ShorterLinkedListMergeInPlace {
    public static void main(String[] args) {
        System.out.println(merge(oddList(), null));                     // [1, 3, 7]
        System.out.println(merge(oddList(), evenList()));               // [1, 2, 3, 4, 6, 7, 10]
        System.out.println(merge(new ListNode(-1, null), evenList()));  // [-1, 2, 4, 6, 10]
        System.out.println(merge(new ListNode(100, null), evenList())); // [2, 4, 6, 10, 100]
        System.out.println(merge(evenList(), new ListNode(100, null))); // [2, 4, 6, 10, 100]
    }

    private static ListNode merge(ListNode left, ListNode right) {
        if (left == null) return right;
        if (right == null) return left;

        ListNode head = null, curr = null;
        do {
            boolean takeLeft = left.val <= right.val;
            ListNode selected = takeLeft ? left : right;

            if (head == null) head = curr = selected;
            else curr = curr.next = selected;

            if (takeLeft) left = left.next;
            else right = right.next;
        } while (left != null && right != null);

        if (left == null) curr.next = right;
        else curr.next = left;

        return head;
    }

    private static ListNode evenList() {
        return new ListNode(2, new ListNode(4, new ListNode(6, new ListNode(10, null))));
    }

    private static ListNode oddList() {
        return new ListNode(1, new ListNode(3, new ListNode(7, null)));
    }

    private static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val, ListNode next) {
            this.next = next;
            this.val = val;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder("[" + val);
            ListNode node = next;

            while (node != null) {
                sb.append(", ").append(node.val);
                node = node.next;
            }

            return sb.append("]").toString();
        }
    }
}