反转链表，（5）

浅浅的花香味﹌ 2022-06-09 10:08 58阅读 0赞

实现链表的反转，比如原来是 1->2->3->4->5；翻转后就是 5->4->3->2->1，

![Center][]

思路是：首先定义pNode指向头结点，pRrev指向NULL，pNext指向NULL，在链表非NULL的情况下，让 pNext = pNode->m\_pNext; 也就是pNext指向了第二个节点，这时候如果pNext ==NULL了，说明已经到达了原链表的尾部节点，否则执行第一次反转，（1）pNode->m\_pNext = pPrev;让第一个节点的m\_pNext指向NULL，这时候pPrev还是NULL的。（2）pPrev = pNode;让pRrev指向第一个节点（2）pNode = pNext;pNode后移一个节点，接着如果pNode不为NULL，执行第二次循环。第二次循环会反转第二个节点，一次类推。

ListCommon.h 依赖：

[链表基本操作的函数实现。（1）][1]

#include <iostream>
    #include "ListCommon.h"
    
    using namespace std;
    
    ListNode* reversedListNode(ListNode* pHead){
    	if(pHead == NULL)
    		return NULL;
    
    	ListNode* pReversedHead = NULL;
    	ListNode* pNode = pHead;
    	ListNode* pNext = NULL;
    	ListNode* pPrev = NULL;
    
            cout << "original list:"<<endl;
    	PrintList(pHead);
    
    	while(pNode != NULL){
    		pNext = pNode->m_pNext;
    	//pNext等于null，说明已经到达尾部，
    		if(pNext == NULL){
    			pReversedHead = pNode;
    		}
    	//开始处理反转，第一次循环，反转第一个节点，第二次反转第二个节点...
    		pNode->m_pNext = pPrev;
    		pPrev = pNode;
    		pNode = pNext;
    	}
    	cout << "reversed list:"<<endl;
    	PrintList(pReversedHead);
    	return pReversedHead;
    }	
    
    int main(int argc, char* args[]){
    	ListNode* pNode1 = CreateListNode(1);
    	ListNode* pNode2 = CreateListNode(2);
    	ListNode* pNode3 = CreateListNode(3);
    	ListNode* pNode4 = CreateListNode(4);
    	ListNode* pNode5 = CreateListNode(5);
    
    	ConnectListNodes(pNode1,pNode2);
    	ConnectListNodes(pNode2,pNode3);
    	ConnectListNodes(pNode3,pNode4);
    	ConnectListNodes(pNode4,pNode5);
    
    	reversedListNode(pNode1);
    DestoryList(pNode1);
     return 0;
    }

测试结果:

PC:~/algorithm$ g++ ListCommon.cpp ReversedList.cpp -o ReversedList  
PC:~/algorithm$ ./ReversedList  
original list:  
print list begin ---  
1  
2  
3  
4  
5  
print list end  
reversed list:  
print list begin ---  
5  
4  
3  
2  
1  
print list end

[Center]: /images/20220609/e042d1e490c0443c98bb7abb5c8d285f.png
[1]: http://blog.csdn.net/lin20044140410/article/details/77658778