插入法
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) { if(pHead1==NULL) return pHead2; if(pHead2==NULL) return pHead1; struct ListNode * t; struct ListNode * ans; if(pHead1->val>pHead2->val) { t=pHead1; pHead1=pHead2; pHead2=t; } ans=pHead1; while(pHead1->next&&pHead2) { if(pHead1->next->val>pHead2->val) { t=pHead2; pHead2=pHead2->next; t->next=pHead1->next; pHead1->next=t; } pHead1=pHead1->next; } if(pHead1->next==NULL) pHead1->next=pHead2; return ans; }
迭代法(创建一个新链表)
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) { struct ListNode * cur; struct ListNode * result=(struct ListNode *)malloc(sizeof(struct ListNode));//创建一个新的头节点 cur=result; while(pHead1&&pHead2)//这种方式要记住 { if(pHead1->val<=pHead2->val) //哪个链表头节点小从哪个链表拿 { cur->next=pHead1; //取节点 pHead1=pHead1->next;//后移对应链表 } else//同理 { cur->next=pHead2; pHead2=pHead2->next; } cur=cur->next;//将新链表后移 } if(pHead2==NULL) //将剩余的链表拼在后面(这个思路重点) cur->next=pHead1; if(pHead1==NULL) cur->next=pHead2; return result->next; }