【剑指offer】反转链表

    xiaoxiao2022-07-12  137

    题目描述

    输入一个链表,反转链表后,输出新链表的表头。

     【分析】 关于链表的题目虽然简单,但很容易出错。这道题比较不容易出错的办法是,单独定义一个新节点NewH,当找到链表的尾部时,则赋值给NewH作为新链表的头部。而遍历链表,保存下一点的状态,和之前的状态,分别需要三个节点。故一开始就定义好四个节点。代码如下:

    /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == NULL) return nullptr; ListNode* pre= nullptr;//前一个节点 ListNode* NewH = nullptr;//作为将来返回的链表头结点 ListNode* cur = pHead;//当前节点 ListNode* pNext = nullptr;//下一个节点 while(cur!= nullptr){ pNext = cur->next; if(pNext == nullptr)//当当前节点的下一个节点已经为NULL时,则找到新的链表头 NewH = cur; cur -> next = pre; pre = cur; cur = pNext; } return NewH; } };

    当然,也可以这样写:

    class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == NULL) return nullptr; ListNode* NewH= nullptr;//始终跟随当前节点,作为新的头部 ListNode* cur = pHead;//当前节点 ListNode* pNext = nullptr;//下一个节点 while(cur!= nullptr){ pNext = cur->next; cur -> next = NewH; NewH = cur; cur = pNext; } return NewH; } };

     

    最新回复(0)