C语言实现
思路：由于两个链表是排好序了的，那么我们对于这种题的解法可以先创建出一个新的头结点，然后再创建一个指针cur指向这个头结点，然后两个链表的值之间进行比较，利用cur去改变链表的next域，将两个链表串起来，最后肯定会有一方头结点走空，那么我们可以，之后将cur所在节点的next域指向未走空的节点头结点，这样我们就把所有的数据串起来了
具体代码实现:
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) { // write code here //生成一个节点，利用这个节点去把这两个链表进行串起来 struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = newhead; //循环终止条件，如果其中一个头结点为空，那么就跳出循环 while(pHead1!=NULL&&pHead2!=NULL) { //如果更小的是pHead1所在节点，就要串到pHead1，然后pHead1往后走 if(pHead1->val<pHead2->val) { cur->next=pHead1; cur=cur->next; pHead1=pHead1->next; } else { cur->next=pHead2; cur=cur->next; pHead2=pHead2->next; } } //如果pHead1走空，就把剩下的数据串与pHead2连上 if(pHead1==NULL) { cur->next=pHead2; } else { cur->next=pHead1; } //返回生成节点的next即可 return newhead->next; }
JAVA版本
思路：同C语言实现思想一致
具体代码如下：
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { ListNode newNode = new ListNode(-1); ListNode cur = newNode; while(list1!=null&&list2!=null){ if(list1.val<list2.val){ cur.next=list1; list1=list1.next; cur=cur.next; }else{ cur.next=list2; list2=list2.next; cur=cur.next; } } if(list1==null){ cur.next=list2; }else{ cur.next=list1; } return newNode.next; } }
总结：
对于本题我们主要要学习一个傀儡节点的使用，利用傀儡节点可以有效的帮助我们解决这种排序两个链表的问题，主要的其实还是要理解思想，如何去做，代码实现起来还是挺快的，对于链表的习题我会持续的进行更新！如有写的不好的地方，请及时指出，相互学习！！！
