剑指 Offer 24. 反转链表

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

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

解题思路：双指针，就地反转

• 首先定义两个指针 pre,cur，pre是cur的前一个指针，指向cur指向元素的前一个元素 ListNode* pre = NULL;ListNode* cur = head;
• 定义while循环，条件是 cur != NULL
• 然后，我们定义一个暂存的节点tmp指向cur的下一个元素，方便指针向后走 ListNode* tmp = cur->next;
• 我们需要反转链表，那么在循环中局部反转，如何做呢？很显然，让 cur->next = pre即可，这样cur本来向后的指向就指向了前一个元素，达到了反转
• 然后 pre = cur 让pre指向cur ，然后 cur = tmp让cur向后走，直到链表所有元素全部被反转

AC代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL)
        {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};