【剑指offer】合并两个有序的链表

【文章结构】：

1 实现方法1--自己编写  

2 参考剑指offer代码

【我的解题思路】

1 编写一个函数，可以在链表尾部加入节点（linklist.addNodeAtTail(pNew,pNow)）

public Node addNodeAtTail(Node newNode,Node currNode){ Node pNew=currNode; if(currNode==null) { pNew=newNode; head=pNew; tail=pNew; if(newNode!=null) {size++; currNode=pNew;} } else if(newNode!=null){ { currNode.next=newNode; currNode=newNode; tail=newNode; size++; } } return currNode; }2 比较两个有序链表的第一个值，并将最小值添加到新链表中

public void mergeLinklist(Node pHead1,Node pHead2){ Node cuNode=null; while(pHead1!=null||pHead2!=null){ if(pHead1==null||pHead2!=null&&pHead1.value>=pHead2.value) { cuNode=addNodeAtTail(pHead2,cuNode); pHead2=pHead2.next; } else if(pHead2==null||pHead1!=null&&pHead1.value<=pHead2.value) { cuNode=addNodeAtTail(pHead1,cuNode); pHead1=pHead1.next; } } 测试程序及运行结果：

MyLinkList linklist6=new MyLinkList(); //Node addNodeAtTail(Node newNode,Node currNode) Node p1=linklist4.head; Node p2=linklist5.head; //mergeLinklist(p1,p2,linklist6); linklist6.mergeLinklist(p1, p2); //linklist6.mergeLinklist(p1, null); linklist6.print(linklist6.head); the elements in the list : 3 4 5 7 14 the elements in the list : 2 3 6 11 the elements in the list : 2 3 3 4 5 6 7 11 14

【参考答案方法：】

//答案中采用递归方法，递归方法就不用while循环了。。。，之前还一直担心递归结果回去会返回链表的尾节点。。。，哎 学艺不精！

public Node mergeLinklist_Ans(Node pHead1,Node pHead2){ if(pHead1==null) return pHead2; if(pHead2==null) return pHead1; Node mergeNode=null; if(pHead1.value>=pHead2.value){ mergeNode=pHead2; mergeNode.next=mergeLinklist_Ans( pHead1,pHead2.next); } else{ mergeNode=pHead1; mergeNode.next=mergeLinklist_Ans( pHead1.next,pHead2); } return mergeNode; }