NC78 #反转链表#

解法一：双指针
注意点：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);
    }
};