【面试题】剑指offer 17

3/8/2017来源:ASP.NET技巧人气:3582

题目: 输入两个递增的链表,合并两个链表,并返回合并后的头结点

#include<iostream> using namespace std; struct ListNode { int _value; ListNode* pNext; }; class MyList { public: MyList() :pHead(NULL) {} ~MyList() { delete pHead; pHead=NULL; } void addNode(const int value) { ListNode* newnode=new ListNode(); if (pHead==NULL) { newnode->_value=value; newnode->pNext=NULL; pHead=newnode; return; } ListNode* node=pHead; while(node->pNext!=NULL) { node=node->pNext; } newnode->_value=value; newnode->pNext=NULL; node->pNext=newnode; } ListNode* getHead() { return pHead; } PRivate: ListNode* pHead; }; ListNode* MergeList(ListNode* pHead1,ListNode* pHead2) { if (pHead1==NULL) return pHead2; if(pHead2==NULL) return pHead1; ListNode* MerHead=NULL; if(pHead1->_value<pHead2->_value) { MerHead=pHead1; MerHead->pNext=MergeList(MerHead->pNext,pHead2); } else { MerHead=pHead2; MerHead->pNext=MergeList(MerHead->pNext,pHead1); } return MerHead; } void PrintList(ListNode* pHead) { ListNode* node=pHead; while (node) { cout<<node->_value<<" "; node=node->pNext; } cout<<endl; } void test() { cout<<"test:"<<endl; MyList l1; l1.addNode(1); l1.addNode(3); l1.addNode(5); l1.addNode(7); l1.addNode(9); cout<<"l1:"; PrintList(l1.getHead()); MyList l2; l2.addNode(2); l2.addNode(4); l2.addNode(6); l2.addNode(8); l2.addNode(10); cout<<"l2:"; PrintList(l2.getHead()); ListNode* head=MergeList(l1.getHead(),l2.getHead()); cout<<"MergeList:"; PrintList(head); } void test2() { cout<<"test2:"<<endl; MyList l1; l1.addNode(1); l1.addNode(3); l1.addNode(5); l1.addNode(7); l1.addNode(9); cout<<"l1:"; PrintList(l1.getHead()); MyList l2; cout<<"l2:"; PrintList(l2.getHead()); cout<<"MergeList:"; ListNode* head=MergeList(l1.getHead(),l2.getHead()); PrintList(head); } void test3() { cout<<"test3:"<<endl; MyList l1; cout<<"l1:"; PrintList(l1.getHead()); MyList l2; cout<<"l2:"; PrintList(l2.getHead()); cout<<"MergeList:"; ListNode* head=MergeList(l1.getHead(),l2.getHead()); PrintList(head); } #include "List.h" #include<cstdlib> int main() { test(); test2(); test3(); system("pause"); return 0; }

结果