This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

**Example:**

Input:1->2->4, 1->3->4Output:1->1->2->3->4->4

b'

\n\n#### Approach #1 Recursion [Accepted]

\n

\n#### Approach #2 Iteration [Accepted]

\n

\n

'
**Intuition**

We can recursively define the result of a `merge`

operation on two lists as\nthe following (avoiding the corner case logic surrounding empty lists):

\n\n

\nNamely, the smaller of the two lists\' heads plus the result of a `merge`

on\nthe rest of the elements.

**Algorithm**

We model the above recurrence directly, first accounting for edge cases.\nSpecifically, if either of `l1`

or `l2`

is initially `null`

, there is no\nmerge to perform, so we simply return the non-`null`

list. Otherwise, we\ndetermine which of `l1`

and `l2`

has a smaller head, and recursively set the\n`next`

value for that head to the next merge result. Given that both lists\nare `null`

-terminated, the recursion will eventually terminate.

**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nBecause each recursive call increments the pointer to

\n`l1`

or`l2`

by one\n(approaching the dangling`null`

at the end of each list), there will be\nexactly one call to`mergeTwoLists`

per element in each list. Therefore,\nthe time complexity is linear in the combined size of the lists. \n - \n
Space complexity : \n

\nThe first call to

\n`mergeTwoLists`

does not return until the ends of both\n`l1`

and`l2`

have been reached, so stack frames consume\n space. \n

\n

**Intuition**

We can achieve the same idea via iteration by assuming that `l1`

is entirely\nless than `l2`

and processing the elements one-by-one, inserting elements of\n`l2`

in the necessary places in `l1`

.

**Algorithm**

First, we set up a false "`prehead`

" node that allows us to easily return the\nhead of the merged list later. We also maintain a `prev`

pointer, which\npoints to the current node for which we are considering adjusting its `next`

\npointer. Then, we do the following until at least one of `l1`

and `l2`

points\nto `null`

: if the value at `l1`

is less than or equal to the value at `l2`

,\nthen we connect `l1`

to the previous node and increment `l1`

. Otherwise, we\ndo the same, but for `l2`

. Then, regardless of which list we connected, we\nincrement `prev`

to keep it one step behind one of our list heads.

After the loop terminates, at most one of `l1`

and `l2`

is non-`null`

.\nTherefore (because the input lists were in sorted order), if either list is\nnon-`null`

, it contains only elements greater than all of the\npreviously-merged elements. This means that we can simply connect the\nnon-`null`

list to the merged list and return it.

To see this in action on an example, check out the animation below:

\n!?!../Documents/21_Merge_Two_Sorted_Lists.json:1280,720!?!

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nBecause exactly one of

\n`l1`

and`l2`

is incremented on each loop\niteration, the`while`

loop runs for a number of iterations equal to the\nsum of the lengths of the two lists. All other work is constant, so the\noverall complexity is linear. \n - \n
Space complexity : \n

\nThe iterative approach only allocates a few pointers, so it has a\nconstant overall memory footprint.

\n \n

\n

Analysis and recursive solution written by: @emptyset

\nIterative solution written by: @1337c0d3r

\n