1、思路:
- 申请一个头节点phead,和指向头节点的指针p
- l1代表链表1的第一个结点,l2同理
- 判断两个链表是否为空
- 比较l1和l2的大小,小的插入头节点的后面,然后将指针移动到下一位
- 终止条件是l1和l2结点不为空
- 当有一个为空的时候,直接将剩下的结点插在p后面!!
2、代码
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 12 if(l1==NULL) return l2; 13 if(l2==NULL) return l1; 14 ListNode *phead,*p;//定义头节点 15 phead=new ListNode(0); 16 phead->next=NULL; 17 p=phead; 18 while(l1!=NULL&&l2!=NULL){ 19 if(l1->val<=l2->val){ 20 // l1->next=p->next; 21 p->next=l1; 22 l1=l1->next; 23 } 24 else{ 25 // l2->next=p->next; 26 p->next=l2; 27 l2=l2->next; 28 } 29 p=p->next; 30 } 31 p->next=l1!=NULL?l1:l2;//判断哪一个先为空 32 return phead->next; 33 } 34 };