# Sword finger Offer learning summary - merging two sorted lists

This series is the learning summary of sword finger Offer, mainly the analysis and implementation of code cases:
Original author's blog: http://zhedahht.blog.163.com/blog/static/254111742011101624433132/

## Merge two sorted linked lists

### subject

Title: enter two ascending sorted linked lists, merge the two linked lists and make the nodes in the new linked list still rank in ascending order.
For example, input the linked list 1 and 2 in the diagram, and the combined linked list is shown in the linked list 3.

The definition of linked list node is as follows:

```struct ListNode
{
int       m_nKey;
ListNode* m_pNext;
};```

### Solution at first sight:

When we consider merging two linked lists, if we can use a new virtual node.
We can define a new linked list, point to linked list 1 and linked list 2 with two pointers respectively, and compare the data size of nodes pointed to by them,
We select the small data of the two, insert it into the new list, and then move the new list pointer and the selected data pointer.

If it is necessary to merge on the existing chain list, we choose the one with the smaller value of two chain head nodes as the combined head node,
Then move back the head pointer of the selected linked list, and define a new pointer to the new linked list node currently built.

```ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
//Consider the case of empty list

ListNode* pMerged = NULL;
ListNode* p = NULL;

{
}
else
{
}

p = pMerged;//Pointer to the combined linked list

{
{
p = p->m_pNext;

}
else
{
p = p->m_pNext;
}
}
//Judgment of other conditions at the end of the cycle
{
}
{
}
return pMerged;
}```

### The realization of recursion

The above thinking, if we use the idea of recursion to understand, will appear more simple. The premise of recursion is divide and conquer.
We deal with the head node and the back node of the list respectively. Each recursion only deals with the head node and the remaining nodes of the list.

```ListNode* Merge1(ListNode* pHead1, ListNode* pHead2)
{
//Termination condition of recursion

{