反转链表－C++

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程https://www.captainai.net/troubleshooter

// 面试题24：反转链表 // 题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的 // 头结点。 #include <cstdio> #include <stdio.h> #include <stdlib.h> struct ListNode { int m_nValue; ListNode *m_pNext; }; ListNode *CreateListNode(int value) { ListNode *pNode = new ListNode(); pNode->m_nValue = value; pNode->m_pNext = nullptr; return pNode; } void ConnectListNodes(ListNode *pCurrent, ListNode *pNext) { if (pCurrent == nullptr) { printf("Error to connect two nodes.\n"); exit(1); } pCurrent->m_pNext = pNext; } void PrintListNode(ListNode *pNode) { if (pNode == nullptr) { printf("The node is nullptr\n"); } else { printf("The key in node is %d.\n", pNode->m_nValue); } } void PrintList(ListNode *pHead) { printf("PrintList starts.\n"); ListNode *pNode = pHead; while (pNode != nullptr) { printf("%d\t", pNode->m_nValue); pNode = pNode->m_pNext; } printf("\nPrintList ends.\n"); } void DestroyList(ListNode *pHead) { ListNode *pNode = pHead; while (pNode != nullptr) { pHead = pHead->m_pNext; delete pNode; pNode = pHead; } } void AddToTail(ListNode **pHead, int value) { ListNode *pNew = new ListNode(); pNew->m_nValue = value; pNew->m_pNext = nullptr; if (*pHead == nullptr) { *pHead = pNew; } else { ListNode *pNode = *pHead; while (pNode->m_pNext != nullptr) pNode = pNode->m_pNext; pNode->m_pNext = pNew; } } void RemoveNode(ListNode **pHead, int value) { if (pHead == nullptr || *pHead == nullptr) return; ListNode *pToBeDeleted = nullptr; if ((*pHead)->m_nValue == value) { pToBeDeleted = *pHead; *pHead = (*pHead)->m_pNext; } else { ListNode *pNode = *pHead; while (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value) pNode = pNode->m_pNext; if (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue == value) { pToBeDeleted = pNode->m_pNext; pNode->m_pNext = pNode->m_pNext->m_pNext; } } if (pToBeDeleted != nullptr) { delete pToBeDeleted; pToBeDeleted = nullptr; } } ListNode *ReverseList(ListNode *pHead) { ListNode *pReversedHead = nullptr; ListNode *pNode = pHead; ListNode *pPrev = nullptr; while (pNode != nullptr) { ListNode *pNext = pNode->m_pNext; if (pNext == nullptr) pReversedHead = pNode; pNode->m_pNext = pPrev; pPrev = pNode; pNode = pNext; } return pReversedHead; } // ====================测试代码==================== ListNode *Test(ListNode *pHead) { printf("The original list is: \n"); PrintList(pHead); ListNode *pReversedHead = ReverseList(pHead); printf("The reversed list is: \n"); PrintList(pReversedHead); return pReversedHead; } // 输入的链表有多个结点 void Test1() { 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); ListNode *pReversedHead = Test(pNode1); DestroyList(pReversedHead); } // 输入的链表只有一个结点 void Test2() { ListNode *pNode1 = CreateListNode(1); ListNode *pReversedHead = Test(pNode1); DestroyList(pReversedHead); } // 输入空链表 void Test3() { Test(nullptr); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); return 0; } // ------ Output ------ /* The original list is: PrintList starts. 1 2 3 4 5 PrintList ends. The reversed list is: PrintList starts. 5 4 3 2 1 PrintList ends. The original list is: PrintList starts. 1 PrintList ends. The reversed list is: PrintList starts. 1 PrintList ends. The original list is: PrintList starts. PrintList ends. The reversed list is: PrintList starts. PrintList ends. */