Two lists into one

Two chains go in, a third comes out. Every version of this problem is the same loop with a different rule for choosing which value to write next, so learn the frame once and the rule is the only thing you swap.

Before any of that, answer the question that decides the whole method: do the 2 input lists survive? If they have to survive, you build new nodes and never touch an input's arrows. If they are being consumed, you move their nodes into the result, and at the end both inputs have to end up empty, which means their heads and their sizes go to nothing too. Leaving an input pointing at nodes the result now owns is the same quiet bug as a missing sever, and it is worse here because 2 lists are wrong instead of one.

The frame

Build the result with a cursor on its last node. Then writing a value is one attach and one step, forever, and you never walk the result to find its end.

LinkedList out = new LinkedList();
Node tail = out.head;          // the result's sentinel
// ... choose a value ...
tail.next = new Node(value, null);
tail = tail.next;
out.size++;

Give the result a sentinel if you are allowed to, because then the first value written is not a special case. If the result has no sentinel, start tail at null and branch once on the first value, exactly the way the sublist page does it.

One after the other

The simplest rule is to write everything from the first list, then everything from the second. The result reads as one list followed by the other, and no comparison happens anywhere.

Node cur = a.head;
while (cur != null)
{
    tail.next = new Node(cur.data, null);
    tail = tail.next;
    out.size++;
    cur = cur.next;
}
cur = b.head;
while (cur != null)
{
    tail.next = new Node(cur.data, null);
    tail = tail.next;
    out.size++;
    cur = cur.next;
}

2 identical loops are fine. Notice that the second one starts with tail already sitting on the last value the first loop wrote, which is why nothing has to be searched for in between.

If you were allowed to consume the inputs and both lists have no sentinel, there is a much shorter version: walk the first list to its last node, point that node at the second list's head, add the sizes, and empty the second list. No new nodes, one write. The catch is that both lists then share nodes until you empty the second one, so emptying it is part of the operation rather than tidying up afterward.

That shorter version has one case that ruins it: the second list is the same object as the first. Walk to the last node, point it at the second list's head, and you have pointed the last node back at the front of its own chain, with no null anywhere in it. Add the sizes and empty "the second list," and you have emptied the list you meant to keep: its head is null, its size is 0, and every value is gone. Leave out the emptying and it is worse, because the next walk, including the one inside toString, never ends. Check other == this first and do what the comment above the method says for that case, or copy the values the long way, which is safe because it builds new nodes.

Merging 2 sorted lists

Now the inputs are each already in order and the result has to be in order too. The rule for choosing is one comparison: whichever of the 2 front values comes first goes next.

That works because of what sorted means. Each list's front value is the smallest value that list still has, so the smaller of those 2 is the smallest value left anywhere. Take it, step that list forward, and the same claim is true again. Nothing ever has to be reconsidered, which is why one pass over each list is enough.

Node p = a.head;
Node q = b.head;
while (p != null && q != null)
{
    if (((Comparable) q.data).compareTo(p.data) < 0)
    {
        tail.next = new Node(q.data, null);
        q = q.next;
    }
    else
    {
        tail.next = new Node(p.data, null);
        p = p.next;
    }
    tail = tail.next;
    out.size++;
}
while (p != null)                 // whatever is left of a
{
    tail.next = new Node(p.data, null);
    tail = tail.next;
    out.size++;
    p = p.next;
}
while (q != null)                 // whatever is left of b
{
    tail.next = new Node(q.data, null);
    tail = tail.next;
    out.size++;
    q = q.next;
}

Three things in there have reasons.

The main loop ends as soon as either list runs out, because from that moment there is no choice left to make. The 2 loops after it drain whatever remains. Exactly one of them ever runs, and both are written because you do not know in advance which list emptied first.

The comparison is written so a tie takes from the first list. Read the if carefully: it moves from b only when b's value is strictly smaller, so equal values come from a first. That is what makes the merge stable, meaning 2 values that tie come out in the order they went in. When the values are plain numbers this is invisible. When they are objects sorted on one field and carrying others, it is the difference between a predictable answer and a coin toss.

Both halves of the loop test are checked before either value is read. p != null && q != null proves both cursors before the comparison touches p.data or q.data. Drop either half and the merge crashes on whichever list ends first.

Trace it once. a holds 1 4 9 and b holds 2 4 5.

Result: 1 2 4 4 5 9, size 6. Each list was walked once and nothing was compared twice.

Choosing by comparing the 2 lists

The other rules people ask for are the same frame with a different question. Values that appear in both lists: walk both and write a value only when it matches. Values in the first list that are missing from the second: walk the first, and for each value search the second before deciding. Notice the cost difference. On 2 sorted lists you can answer either question in one pass with the merge walk, because the comparison tells you which cursor to advance. On 2 unsorted lists you are searching the second list once per value in the first, which is the cost the official topic list is pointing at when it warns about code that is grossly inefficient.

In the practice APE

No practice APE has a problem that reads 2 lists and writes a third. 2 problems add one list's values to the end of another:

The official topic list names combining 2 lists, so practice the merge on your own, cold. Build 2 lists of integers that are each already sorted, write the merge from a blank line, and run it on 4 pairs: both empty, one empty and one with values, 2 lists whose values interleave, and 2 lists where every value in the first comes before every value in the second. That last pair is the one that makes the main loop end early and the drain do the work.

Readiness check

The one thing to keep

Combining is one loop that writes to a result you hold by its last node, so every value costs one attach and one step. Decide first whether the inputs survive, because that decides whether you copy values or move nodes, and a result that shares nodes with an input is 2 broken lists rather than one. For 2 sorted inputs, compare the front values, take the smaller, advance only that cursor, and let a tie come from the first list so the order you were given survives.