【面试题】剑指offer 17

2019-11-06 06:01:26

字体：大中小

来源：转载

供稿：网友

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

#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;}