338. Concatenate Two Linked Lists

Given the heads of two singly linked lists list1 and list2, concatenate list2 to the end of list1 and return the head of the combined list.

Do not create new nodes — attach list2 directly to the tail of list1.

Input: Heads of two singly linked lists.

Output: Head of the concatenated linked list.

Examples

Input: [1,2,3], [4,5,6]
Output: [1,2,3,4,5,6]
Explanation: Traverse list1 to tail(3). 3.next=head(4). Return list1 head(1).

Input: [], [1,2,3]
Output: [1,2,3]
Explanation: list1 is empty. Return list2 directly.

Input: [1,2,3], []
Output: [1,2,3]
Explanation: list2 is empty. Return list1 unchanged.

Constraints

• 0<=nodes in each list<=10^5
• -10^9<=Node.val<=10^9

Asked by