来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

反转链表I

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

数据交换 swap(i,j) 要定义三个变量 i, j 和 temp，同样要实现链表反转，也必须定义三个指针，ppre, pcur, ptemp。

实现方法1

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL)
            return NULL;
        ListNode* ppre=head;
        ListNode* pcur=ppre->next;
        if(pcur==NULL)
            return head;
        ListNode* ptemp=pcur->next;
        ppre->next=NULL;
        while(ptemp!=NULL)
        {
            pcur->next=ppre;
            ppre=pcur;
            pcur=ptemp;
            ptemp=ptemp->next;
        }
        pcur->next=ppre; //ptemp为空时，最后一个节点还没有反转
        return pcur;
    }
};

实现方法2

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* ppre=NULL;  //虚拟的头节点
        ListNode* pcur=head;
        while(pcur!=NULL)
        {
            ListNode* ptemp=pcur->next;
            pcur->next=ppre;
            ppre=pcur;
            pcur=ptemp;
        }
        return ppre;
    }
};

可以看出，方法2比方法1简洁，这是因为方法2使用了虚拟的头节点，使用虚拟头结点的好处是，可能省掉一些特殊处理，使代码和逻辑更简洁高效。

反转链表II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路比较简单，先找到第m个结点，并记录第m-1个结点和第m个结点，然后一直反转，直到第n个结点，记录第n个结点和第n+1个结点，最后重建链表，m-1->next=n,m->next=n+1即可。
时间复杂度最差 o(n) ，空间复杂度 o(1)。

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == NULL || head->next == NULL) //处理空链表或只含一个结点的链表
            return head;
        ListNode* ppre = NULL; // 设置虚拟头节点
        ListNode* pm = head;
        int k = 1;
        while (k<m)
        {
            ppre = pm;
            pm = pm->next;
            ++k;
        }//结束后 k=m,ppre是第m-1个结点 pm是第m个结点

        ListNode* pm_s = pm; // 记录此时第m个结点的位置，最后重建链表需要用到
        ListNode* pcur = pm->next; //用pm pcur ptmp反转链表 
        while (m<n)
        {
            ListNode* ptmp = pcur->next;
            pcur->next = pm;
            pm = pcur;
            pcur = ptmp;
            ++m;
        }//结束后 pm是第n个结点,pcur是第n+1个结点
        // 四个指针 ppre pm_s pm pcur重建链表
        pm_s->next = pcur;
        if (ppre)    //ppre不为空 m!=1，表头是head   
        {
            ppre->next = pm;
            return head;
        }
        return pm;  //ppre为空，m=1 ,表头为pm ,如 [1,2,3,4],m=1,n=3 
    }
};

细节：

关于 p->next=q 和 q=p->next，每次做链表题目都会卡在这里，一想就乱，耗费心智。
可以类比 a=b 和 b=a，一个是前者是改变 a 的值，后者是改变 b 的值。
对应 p q 来说，前者是改变 p->next，也就是改变 p的下一个结点，而后者只是改变 q 的值， 使 q 与 等于p 的下一个结点 。所以前者可以改变指针的指向。

图片

图片转载自：<https://blog.csdn.net/weixin_44135282/article/details/90348885>