Why does Iterator.iterate never call _.next on null?

Iterator.iterate(start)(f) computes the next element only when it is asked for one. After the last node, it produces null, takeWhile(_ != null) rejects it and the iterator ends, so f is never applied to null. An empty list starts with null and ends at once.

Why foldRight(null: ListNode) and not foldRight(null)?

The start value fixes the type of the accumulator. A bare null would be inferred as Null, and the function returning a ListNode would not fit. The type ascription null: ListNode makes the accumulator a ListNode that starts empty.

Can I add @tailrec to the recursive merge?

No. @tailrec requires the recursive call to be the last thing the method does, and here its result is stored in next first. The annotation would turn that into a compile error. An accumulator version that carries the tail of the result can be tail recursive, but it is the dummy-head loop in another form.

Why is the value field x and not val?

val is a Scala keyword, so the node class names its value x (with next for the link), the shape Scala solvers are usually given. Read it as node.x.

How do I merge two sorted immutable Lists in Scala?

Pattern matching gives a short recursive merge: case (Nil, ys) => ys, case (xs, Nil) => xs, and for (x :: xt, y :: yt) put the smaller head in front of the merge of the rest. It is not tail recursive either, so long lists are better merged with a ListBuffer in a loop. (xs ++ ys).sorted is the O(n log n) shortcut.

EasyLinked list

Merge Two Sorted Lists

You get list1 and list2, the first nodes of two singly linked lists. Every list node holds an integer val and a pointer next to the node after it; the last node's next is empty. Each list is sorted in ascending order, and values can repeat, inside one list and across both. Return the head of a single list that holds every value of both lists, also in ascending order. Equal values all stay: a value that appears twice in total appears twice in the result.

Either list can be empty, which means it has no nodes at all. If one list is empty, the result is the other list; if both are empty, return an empty list. You may relink the nodes you were given or build new ones; only the values in the result, from head to tail, are checked.

In the examples and test cases a list is written as an array of its values from head to tail, so [2, 5, 11] is the node 2 pointing at 5 pointing at 11.

Examples

Input

list1 = [2, 5, 11]
list2 = [3, 4, 12, 20]

Output[2, 3, 4, 5, 11, 12, 20]WhyAt each step the smaller of the two front values goes next: 2, then 3 and 4 from list2, then 5 and 11. Once list1 runs out, the rest of list2 (12, 20) follows as it is.

Input

list1 = [6, 6, 9]
list2 = [1, 6]

Output[1, 6, 6, 6, 9]WhyDuplicates are kept: 6 appears twice in list1 and once in list2, so the result holds three 6s.

Constraints

Size: 0 ≤ nodes in list1, nodes in list2 ≤ 300
Values: -10⁹ ≤ val ≤ 10⁹
Order: Both lists are sorted ascending; values can repeat.
Answer: Return the head of the merged ascending list; two empty lists merge to an empty list.
Time limit: 10 s per run, all cases

merge_two_lists.scala

Scala 3.6

Not run yet

+ 8 hidden

Input

list1 = [2, 5, 11]
list2 = [3, 4, 12, 20]

Expected

[2, 3, 4, 5, 11, 12, 20]

At each step the smaller of the two front values goes next: 2, then 3 and 4 from list2, then 5 and 11. Once list1 runs out, the rest of list2 (12, 20) follows as it is.