// 面试题24：反转链表 // 题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的 // 头结点。 #include <cstdio> #include "List.h" ListNode* ReverseList(ListNode* pHead) { ListNode* pRevHead = nullptr; ListNode* pNode = pHead; //当前节点 ListNode* pPrev = nullptr; //前一个节点 while (pNode != nullptr) { ListNode* pNext = pNode->m_pNext; //如果到了尾节点 if (pNext == nullptr) pRevHead = pNode; pNode->m_pNext = pPrev; //当前节点连接到上一个节点 pPrev = pNode; pNode = pNext; } return pRevHead; }
// ====================测试代码==================== 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; }
分析：多考虑边界值。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* pRevHead = nullptr; ListNode* pNode = pHead; ListNode* pPrev = nullptr; while (pNode != nullptr) { ListNode* pNext = pNode->next; if (pNext == nullptr) pRevHead = pNode; pNode->next = pPrev; pPrev = pNode; pNode = pNext; } return pRevHead; } };
原文：https://www.cnblogs.com/ZSY-blog/p/12578490.html
