C++算法之 合并两个有序链表

<span style="color:#000000;">// 合并链表.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; struct ListNode { int m_Data; ListNode* m_pNext; ListNode(int value,ListNode* next = NULL):m_Data(value),m_pNext(next){} }; /* 两个链表 比如链表1： 1->3->5->7->9 链表2： 2->4->6->8->10 跟我们合并两个数组1样，链表1的头结点 和链表2的头节点比较，如果链表1头节点的值大于链表2头接点的值， 那末链表2的头结点为合并链表的头结点，那末链表1的头节点继续和链表2的第2个节点（剩余链表2的头结点） 作比较，但1个链表遍历完以后，如果另外1个链表还没有遍历完，由于链表本来就是排序的，所以让合并链表的 尾巴节点指向未遍历完链表的头结点就能够 举个例子： 链表1： 1，3，5，23，34； 链表2： 2，4，6，8，10； 当遍历以后 链表3：1，2，3，4，8，10 此时链表2已遍历完，while循环退出，但是剩余链表1还有 23，34 此时 让链表3的尾巴节点10 链接 剩余链表的头节点 23 就能够了 */ ListNode* MergeList2(ListNode* head1,ListNode* head2) { if (head1 == NULL) { return head2; } else if(head2 == NULL) { return head1; } ListNode* MergeHead = NULL; if (head1->m_Data < head2->m_Data) { MergeHead = head1; head1 = head1->m_pNext; } else { MergeHead = head2; head2 = head2->m_pNext; } ListNode* tmpNode = MergeHead; while (head1&&head2) { if (head1->m_Data < head2->m_Data) { MergeHead->m_pNext = head1; head1 = head1->m_pNext; } else { MergeHead->m_pNext = head2; head2 = head2->m_pNext; } MergeHead = MergeHead->m_pNext; } if (head1) { MergeHead->m_pNext = head1; } if (head2) { MergeHead->m_pNext = head2; } return tmpNode; } int _tmain(int argc, _TCHAR* argv[]) { ListNode* pHead1 = new ListNode(1); ListNode* pCur = pHead1; for (int i = 3; i < 10; i+=2) { ListNode* tmpNode = new ListNode(i); pCur->m_pNext = tmpNode; pCur = tmpNode; } ListNode* pHead2 = new ListNode(2); pCur = pHead2; for (int j = 4; j < 10; j+=2) { ListNode* tmpNode = new ListNode(j); pCur->m_pNext = tmpNode; pCur = tmpNode; } ListNode* head = MergeList2(pHead1,pHead2); while (head) { cout<<head->m_Data<<" "; head=head->m_pNext; } getchar(); return 0; }</span>

// 合并链表.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; struct ListNode { int m_Data; ListNode* m_pNext; ListNode(int value,ListNode* next = NULL):m_Data(value),m_pNext(next){} }; /* 我们分析两个链表的进程，首先从合并两个链表的头结点开始，链表1的头节点的值小于链表2的头结点的值，因此链表1的头结点 就是合并链表的头节点，继续合并剩下的链表，在两个链表中剩余的节点依然是排序的，因此合并两个链表的步骤是1样的，我们还是比较两个头结点的 值，此时链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是合并剩余链表的头结点，我们把这个节点和前面合并链表时得到的链表的尾巴节点 链接起来 依照上面的分析可知：每次合并的步骤都是1样的，由此我们想到了递归。 */ ListNode* MergeList(ListNode* pHead1,ListNode* pHead2) { if (pHead1 == NULL) { return pHead2; } else if (pHead2 == NULL) { return pHead1; } ListNode* pMergeHead = NULL; if (pHead1->m_Data < pHead2->m_Data) { pMergeHead = pHead1; pMergeHead->m_pNext = MergeList(pHead1->m_pNext,pHead2); } else { pMergeHead = pHead2; pMergeHead->m_pNext = MergeList(pHead1,pHead2->m_pNext); } return pMergeHead; } int _tmain(int argc, _TCHAR* argv[]) { ListNode* pHead1 = new ListNode(1); ListNode* pCur = pHead1; for (int i = 3; i < 10; i+=2) { ListNode* tmpNode = new ListNode(i); pCur->m_pNext = tmpNode; pCur = tmpNode; } ListNode* pHead2 = new ListNode(2); pCur = pHead2; for (int j = 4; j < 10; j+=2) { ListNode* tmpNode = new ListNode(j); pCur->m_pNext = tmpNode; pCur = tmpNode; } ListNode* head = MergeList2(pHead1,pHead2); while (head) { cout<<head->m_Data<<" "; head=head->m_pNext; } getchar(); return 0; }

<span style="color:#000000;">// MergeArray.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; //递归方法 void MergeArray2(int a[],int aCount,int b[],int blen) { int len = aCount+blen⑴; aCount--; blen--; if (aCount < 0) { while (blen>=0) { a[len--] = b[blen--]; } return; } if (a[aCount] > b[blen]) { a[len] = a[aCount]; MergeArray2(a,aCount,b,++blen); } else { a[len] = b[blen]; MergeArray2(a,++aCount,b,blen); } } void MergeArray(int a[], int aCount, int b[], int blen)//aCount为a数组实际（狭义）长度，blen为b数组实际长度 { int len = aCount + blen - 1;//合并数组的长度也就是a数组的广义长度 aCount--; blen--; while (aCount>=0 && blen>=0) { if (a[aCount] >= b[blen]) { a[len--] = a[aCount--]; } else { a[len--] = b[blen--]; } } while(blen >= 0) { a[len--] = b[blen--]; } } int _tmain(int argc, _TCHAR* argv[]) { int a[] = {2,4,6,8,10,0,0,0,0,0}; int b[] = {1,3,5,7,9}; MergeArray2(a,5,b,5); for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++) { cout<<a[i]<<" "; } getchar(); return 0; }</span>