Personal website: www.cxyxiaowu.com

The title comes from Problem no. 21 in LeetCode: Merge two ordered lists. The difficulty of the questions is Easy, with a pass rate of 45.8% so far.

### Topic describes

Merges two ordered lists into a new ordered list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Example:

``Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code``

### title

#### General plan

##### 1.2 Code Implementation
``````ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* pTail = NULL;// connect to pTail->next
ListNode* newHead = NULL;// point to the first node of the merged list
}else{
}else{
}
pTail = newHead;// point to the first node
}else {
}
pTail = pTail->next;

}
}
}
Copy the code``````

#### 2. Recursive scheme

##### 2.1 Idea of problem solving

(1) Handle the existence of an empty linked list. If pHead1 is empty, pHead2 is returned, and pHead1 is returned if pHead2 is empty. (2) Compare the size of the first node of the two linked lists to determine the position of the head node. (3) After the head node is determined, continue to select the next node from the remaining nodes to link to the node selected in the second step, and then repeat steps (2) and (3) until there is no linked list.

##### 2.2 Code Implementation
``````ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){