剑指offer24 反转链表

题目

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

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制： 0 <= 节点个数 <= 5000

思路

双指针

选择双指针迭代的方法。

/**
 * 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 *p = head,*pre = NULL;
        
        while(p) {
            ListNode *temp = p->next;//暂存当前结点的后继
            p->next = pre;
            //双指针同时后移
            pre = p;
            p =temp;
        }
        return pre;
    }
};

遍历聊表，使用pre指针指向当前结点的上一个结点，改变指针指向，让结点指向pre带便的结点，可以由此完成反转。

1. 用temp指针存储当前结点p的后继
2. 当前结点p指向pre也就是当前结点P的前驱(初始为空)
3. pre和p一起后移
4. 最后一次后移时,p指向了空,pre指向了最后一个结点，返回pre就行了 一张图可以很好的理解：

递归

递归与前一种方法本质是相同的，不过他用递归完成了指针后移

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode* df(ListNode *p,ListNode *pre) {
        if(p == NULL) return pre;
        ListNode *temp = p->next;//暂存一下p的后继
        p->next = pre;
        return df(temp,p);
    }

    ListNode* reverseList(ListNode* head) {
        return df(head,NULL);//相当于进行了初始化，ListNode* cur = head,*pre = NULL;
    }

};

使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点pre，每次递归时都改变一下结点指针的方向就行了。当然也可以先递归寻找结点，再从链表末尾开始每一层递归中修改指针方向，这样递归写法就不同了。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return df(head, NULL);           // 调用递归并返回
    }
    ListNode* df(ListNode *p, ListNode *pre) {
        if (p == NULL) return pre;        // 终止条件
        ListNode* temp = df(p->next, p); // 递归后继节点
        p->next = pre;// 修改节点引用指向
        return temp;// 返回反转链表的头节点
    }
};