### 1. Merge two sorted linked lists and return it as a new list.

Example:

``````- Input: 1 -> 3-> 5 & 2 -> 4-> 6
Output: 1 -> 2-> 3 -> 4 -> 5 -> 6
``````

Approach:

``````- Traverse both list at the same time, compare their values at each step and
add the smaller one to a new list.
``````

Cost:

``````- O(n|m) time, O(n+m) space where n and m are lengths of these two linked lists.
``````

### 2. Given two linked lists representing two non-negative number, add them together and return it as a linked list.

Assumption:

``````- The digits are stored in reverse order.
- Each node contains a single digit.
``````

Example:

``````- Input: (1 -> 6 -> 4) + (2 -> 4-> 1)
Output: (3 -> 0 -> 6)
``````

Approach:

``````- Traverse both lists and keep track of the sum and carry for each
digit.
``````

Cost:

``````- O(n|m) time, O(m|n) space where m and m are lengths of these two lists.
``````

Assumption:

``````- If the length of the linked list is odd, the last node should not be swapped.
- The solution should use constant space.
``````

Example:

``````- Input: 1 -> 3-> 5 -> 2 -> 4-> 6
Output: 3 -> 1-> 2 -> 5 -> 6 -> 4
- Input: 1 -> 3-> 5 -> 2 -> 4
Output: 3 -> 1-> 2 -> 5 -> 4
``````

Approach:

``````- Traverse the list and swap the nodes pairwise by adjusting where it's pointing next.
``````

Cost:

``````- O(n) time, O(1) space where n is the length of a linked list.
``````