Leetcode——206反转链表

反转一个单链表。

示例:

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

首选对于链表问题，最好的解决方法就是，拿张纸画出来。

我们的思路就是利用双指针

• 定义两个指针： pre和 cur ；pre在前 cur在后。
• 每次让 pre的 next指向 cur，实现一次局部反转
• 局部反转完成之后， pre和 cur同时往前移动一个位置
• 循环上述过程，直至 pre到达链表尾部

第一步

第二步

第三步

第四部

这样直到最后pre节点为空的时候停止

/**
 * 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 = NULL;
        ListNode* pre = head;
        while(pre != NULL){
            ListNode* t = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};