C++算法之 反转单链表 |
您所在的位置：网站首页 › 链表的反转 › C++算法之 反转单链表 |
|
题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点，链表节点定义为： struct ListNode ｛ int m_nValue; ListNode* m_pNext; ｝; 算法思路： 链表 1-->2-->3-->4-->5 建立一个 pPrev节点，而且为空节点； pPrev = NULL；再建立一个节点pNode = pHead; 再建立第三个节点pNext = pNode->m_pNext; pNext的作用：用来保存pNode后面一个的节点，防止链表在中间断开，然后pPrev与pNode往下遍历： 看代码： ListNode* ReverseList(ListNode* head) { ListNode* pNode = head; ListNode* pPrev = NULL; while (pNode != NULL) { ListNode* pNext = pNode->m_pNext;//保存下一个节点的值 pNode->m_pNext = pPrev;//把当前pNode的下一个节点指向pPrev pPrev = pNode;//此时pPrev向后移动指向此时的pNode pNode = pNext;//而pNode也向后移动，指向刚才保存的pNext; } return pPrev; // return pReversedHead; }完整代码： // ReverseList.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include using namespace std; struct ListNode { int m_nValue; ListNode* m_pNext; ListNode() { } ListNode(int i):m_nValue(i),m_pNext(NULL) { } }; void AddToTail(ListNode* pHead, int value) { ListNode* pNew = new ListNode(); pNew->m_nValue = value; pNew->m_pNext = NULL; if (pHead == NULL) { pHead = pNew; } else { ListNode* pNode = pHead; while (pNode->m_pNext!=NULL) { pNode = pNode->m_pNext; } pNode->m_pNext = pNew; } } void Print(ListNode* head) { ListNode* pNode = head; while (pNode!=NULL) { coutm_pNext = pPrev; pPrev = pNode; pNode = pNext; } return pPrev; // return pReversedHead; } int _tmain(int argc, _TCHAR* argv[]) { /* ListNode* head = new ListNode(1); ListNode* node1 = new ListNode(2); ListNode* node2 = new ListNode(3); ListNode* node3 = new ListNode(4); ListNode* node4 = new ListNode(5); head->m_pNext = node1; node1->m_pNext = node2; node2->m_pNext = node3; node3->m_pNext = node4; node4->m_pNext = NULL; */ ListNode* pNode1 = new ListNode(1); //Print(pNode1); AddToTail(pNode1,2); AddToTail(pNode1,3); AddToTail(pNode1,4); AddToTail(pNode1,5); cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |