解法一:双指针
注意点:left要初始化为NULL
class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* left = NULL, *right = pHead; while(right) { ListNode* temp = right->next; right->next = left; left = right, right = temp; } return left; } };
解法二:递归
class Solution { public: ListNode* dfs(ListNode* pre, ListNode* now) { if(!now) return pre; ListNode* temp = now->next; now->next = pre; return dfs(now, temp); } ListNode* ReverseList(ListNode* pHead) { return dfs(nullptr, pHead); } };
不知道为什么这样写就会堆栈溢出:
class Solution { public: ListNode* dfs(ListNode* pre, ListNode* now) { ListNode* temp = now->next; now->next = pre; if(temp) return dfs(now, temp); else return now; } ListNode* ReverseList(ListNode* pHead) { return dfs(nullptr, pHead); } };