[검지offer 면접문제 17] 두 개의 서열을 합친 체인표

 1 #include <iostream>

 2 using namespace std;

 3 

 4 struct ListNode

 5 {

 6     int val;

 7     ListNode *next;

 8     ListNode(int v = 0):val(v), next(NULL){}

 9 };

10 

11 ListNode *SortedListMerge(ListNode *phead1, ListNode *phead2)

12 {

13     if(phead1 == NULL)

14         return phead2;

15     else if(phead2 == NULL)

16         return phead1;

17 

18     ListNode *pMergedHead = NULL;

19 

20     if(phead1->val < phead2->val)

21     {

22         pMergedHead = phead1;

23         pMergedHead->next = SortedListMerge(phead1->next, phead2);

24     }

25     else

26     {

27         pMergedHead = phead2;

28         pMergedHead->next = SortedListMerge(phead1, phead2->next);

29     }

30 

31     return pMergedHead;

32 }

33 

34 int main()

35 {

36 

37     ListNode *l1 = new ListNode(1);

38     ListNode *h1 = l1;

39     for(int i = 3; i <= 11; i += 2)

40     {

41         ListNode *temp = new ListNode(i);

42         l1->next = temp;

43         l1 = l1->next;

44     }

45 

46     ListNode *l2 = new ListNode(2);

47     ListNode *h2 = l2;

48     for(int i = 4; i <= 12; i += 2)

49     {

50         ListNode *temp = new ListNode(i);

51         l2->next = temp;

52         l2 = l2->next;

53     }

54 

55     cout<<"List1: ";

56     ListNode *print1 = h1;

57     while(print1 != NULL)

58     {

59         cout<<print1->val<<" ";

60         print1 = print1->next;

61     }

62     cout<<endl;

63 

64     cout<<"List2: ";

65     ListNode *print2 = h2;

66     while(print2 != NULL)

67     {

68         cout<<print2->val<<" ";

69         print2 = print2->next;

70     }

71     cout<<endl;

72 

73     ListNode *mergeList = SortedListMerge(h1, h2);

74 

75     cout<<"ListMerge: ";

76     ListNode *printlist = mergeList;

77     while(printlist != NULL)

78     {

79         cout<<printlist->val<<" ";

80         printlist = printlist->next;

81     }

82     cout<<endl;

83 

84 

85 }

List1: 1 3 5 7 9 11

List2: 2 4 6 8 10 12

ListMerge: 1 2 3 4 5 6 7 8 9 10 11 12