递归:
函数返回的是反转后的头节点,即固定为原链表中最后一个节点,所以当前函数的返回值应该与递归函数的返回值是一样的。
反转之后应该由原链表中pHead->next指向的节点指向pHead,同时考虑pHead是反转后尾部的情况,应该把pHead->next置为nullptr。
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead || !pHead->next) return pHead; ListNode* newhead = ReverseList(pHead->next); pHead->next->next = pHead; pHead->next = nullptr; return newhead; } };
迭代:
设置bef与now两个节点,now指向当前需要反转的节点,bef指向原链表中now的上一个节点,每次迭代就将now->next设置为bef,由于设置之后会丢失now->next原来的值,所以需要事先用nxt存储now->next原来的值,并在之后赋值给now,now的值赋给bef实现右移。
在循环的最后,now是nullptr,而bef指向now在原链表中的上一个节点,即为原链表的尾部,也是新链表的头部,所以返回bef。
class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* bef = nullptr, *now = pHead; while (now) { ListNode* nxt = now->next; now->next = bef; bef = now; now = nxt; } return bef; } };