1、简介

链表的反转是面试中比较常考的一个点，在这里总结了反转链表的几种题型和要点。

2、题型

2.1 反转链表

2.1.1 问题描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。 alt

2.1.2 实现思路

我们可以回想头插法建立链表的过程，如果想建立顺序为 1 2 3 4 5 6 的链表，用头插法时插入的顺序必须为：6 5 4 3 2 1。由此得出，我们可以模拟头插法来反转链表。

2.1.3 代码实现

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex = nullptr; 
        while (cur) {
            nex = cur->next; //保存后继结点的位置
            cur->next = pre; //前驱变后继
            pre = cur; //当前就变成前驱
            cur = nex; //后继变当前
        }
        return pre;
    }
};

反转流程
（1）保存当前结点的后继
（2）前驱变后继
（3）当前变前驱
（4）后继变当前

2.2 链表指定区间内反转

2.2.1 问题描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

2.2.2 实现思路

我们只需要走到第m个结点处，把m-n个结点反转完拼接在m结点的前驱结点上。所以我们也要定义一个指向m结点前驱结点的指针。

2.2.3 代码实现

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(0); //设置伪结点
        dummy->next = head;
        ListNode* pre = dummy, * cur = head;
        //到第m个结点位置
        for (int i = 1; i < m; i++) {
            pre = pre->next;
        }
        cur = pre->next;
        ListNode* nex = nullptr; //用于保存后继结点
        //在指定范围内进行结点的反转
        for (int i = 0; i < n - m; i++) {
            nex = cur->next; //保存后继结点
            cur->next = nex->next; 
            nex->next = pre->next;
            pre->next = nex;
        }
        return dummy->next;
    }
};

对于上述实现，我们并没有把m-n个结点全部反转完再拼接到原链表上，而是每一步反转一个结点。这样的话时间和空间的开销都会比较少。

比如说要反转的结点为 ABCDEFG 中的 BCDE 结点，上述反转过程为 ACBDEFG -> ADCBEFG -> AEDCBFG。

2.3 链表中的节点每k个一组翻转

2.3.1 问题描述

alt

2.3.2 实现思路

我们可以模拟一下k个一组反转：

首先，计算链表长度，反转区间个数=链表长度 / 区间长度。新增头结点；
然后，针对每个区间，反转区间；
最后，返回答案链表；

2.3.3 代码实现

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head) return head;
        ListNode *p=head;
        int n=0;//链表长度
        while(p)
        {
          	//统计链表长度
        	 n++;
           	 p=p->next;
        }
        int cnt=n/k;//反转区间的个数
        ListNode *h=new ListNode(0); //新增头结点（伪结点）
        h->next=head;
        //初始化
        ListNode *r=h;//r表示区间的前一个节点
        p=head;
        ListNode *q=head->next;
        ListNode *s,*t;//s表示区间的第一个节点
        while(cnt--){//循环cnt个区间
            s=p;
            for(int i=0;i<k-1;i++)
            {	
              	//循环反转区间
                t=q->next;
                q->next=p;
                p=q;
                q=t;
            }
            r->next=p;//反转区间拼接
            s->next=q;
            
            r=s;//再次初始化
            p=q;
            q=q->next;
        }
        return h->next;
    }
};

反转链表专题