反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

思路1：

直观思路，定义两个指针，一个指向当前节点，一个指向前一个节点，每次把当前节点的next指向前一个节点，然后当前指针指向变换前的next，前一个指针指向当前指针。重复这个过程，直到当前指针指向nullptr

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

思路2:

逆向思路，递归。函数的签名是ListNode reverseList(ListNode head),简记为f(x)=y,其中y表示返回值头节点ListNode*，x表示入参head。显然有f(x)==f(x.next),即有这种形式的代码

ListNode* reverseList(ListNode* head) {
    if(head == nullptr) return nullptr;
    ListNode* newHead = reverseList(head->next);
    return newHead;
}

现在需要处理指针反转的代码:整体考虑f(x)的功能，f(x)是把头节点为x的链表反转。上面第三行代码执行完之后，可以认为头节点为x.next的链表已经反转了。所以现在只剩一个节点没有处理就是最开始的head。把这个节点处理掉就完工了。如何反转x和x.next？很显然有x.next.next = x。x = nullptr。反映在实际代码中就是如下代码:

ListNode* reverseList(ListNode* head) {
    if(head == nullptr) return nullptr;
    ListNode* newHead = reverseList(head->next);
    //反转head和head->next
    head->next->next = head;
    head = nullptr;
    return newHead;
}