反转链表共有三个题目：

• 原地单链表反转
• 两个一组反转链表
• K个一组反转链表

  简单的反转链表

  

  https://leetcode-cn.com/problems/reverse-linked-list/

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

思路

迭代法

思路一：不断更新cur和pre，遍历前进

在这个例子中，循环的结果是这样的：
第一次循环的结果：null<-1 2->3->4->5
第二次循环的结果：null<-1<-2 3->4->5
第三次循环的结果：null<-1<-2<-3 4->5
第四次循环的结果：null<-1<-2<-3<-4 5
第五次循环的结果：null<-1<-2<-3<-4<-5

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
          if(!head) return NULL;

        ListNode *pre = NULL, *cur = head;
        ListNode *nx = NULL;
        while(cur != NULL) {
            nx = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nx;
        }
        return pre;
    }
};

思路二：固定cur和pre，遍历前进

在这个例子中，我们固定 pre 为 NULL，cur 为 1
第一次循环的结果：null->2->1->3->4->5
第二次循环的结果：null->3->2->1->4->5
第三次循环的结果：null->4->3->2->1->5
第三次循环的结果：null->5->4->3->2->1

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
          if(!head) return NULL;

        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy, cur = pre->next;

        while(cur != NULL) {
            ListNode *nx = cur->next;
            cur->next = nx->next;
            nx->next = pre->next;
            pre->next = nx;
        }

        return dummy->next;
    }
};

递归法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)
            return head;

        ListNode *p = reverseList(head->next);
        head->next->next = head;    // 进行反转
        head->next = NULL;
        return p;
    }
};

区间反转

https://leetcode-cn.com/problems/reverse-linked-list-ii/

思路：

迭代法

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(!head)
            return NULL;

        ListNode *dummy = new ListNode(-1);
        dummy->next = head;

        ListNode *pre = dummy;
        for(int i = 1; i < m; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        for(int i = m; i < n; i++) {
            ListNode *nx = cur->next;
            cur->next = nx->next;
            nx->next = pre->next;
            pre->next = nx;
        }

        return dummy->next;
    }
};