描述

在一个单链表中，在一次遍历中原地逆转从位置m到位置n的元素（1<=m<n<=list length）。

输入：

1->2->3->4->5->nullptr, m=2,n=4

返回：

1->4->3->2->5->nullptr

分析

在单链表能直接了解到的是链表头和下一个元素，能操作的元素也只有当前指针指向的元素，在操作当前元素时要记录当前元素的下一个元素。

1，设定三个指针:

​ pCur初始值指向原始链表的头元素，pCur=pHead；

​ pNext初始值设置为当前元素的下一个元素pNext=pCur->next

​ pHead2初始值为nullptr，指向新链表的头，pHead2 = nullptr;

2，操作当前指向的指针：

​ 将pCur指向的元素从原始链表中拆解出来，采用头插法添加到pHead2指向的链表并更新头元素的位置：

  ```

pCur->next = pHead2->next;
pHead2->next = pCur;
```

3，更新下一步要在原始链表中操作的元素

pCur = pNext;
pNext = pNext->next;

若pCur不为空，则继续2、3步操作，直到pCur指向为空。

如图：

逆转单列表

考虑区间的逆转：

1，寻找第m个元素及第m-1个元素；

2，从m开始进行(n-m)次头插入操作；

3，将新的链表链接到第m-1个元素后面；

4，将新的链表尾部和第n+1个元素链接；

5，考虑整个链表逆转时的头指针的更新；

实现

​

ListNode* reverseListM2N(ListNode *head, int m, int n)
{
    //需要的变量
    ListNode resultNode(0);
    resultNode.next = head;
    
    //第m个节点
    ListNode *pNodeM = head;
    ListNode *pNodeBeforeM = nullptr;
    
    for(int i=1; i<m; i++) {
        pNodeBeforeM = pNodeM;
        pNodeM = pNodeM->next;
    }
    
    //逆置节点
    ListNode *pHeadTmp = nullptr;
    ListNode *pCur = pNodeM;
    for (int i=0; i<(n-m)+1 && pCur; i++) {
        ListNode *pNext = pCur->next;
        pCur->next = pHeadTmp;
        pHeadTmp = pCur;
        pCur = pNext;
    }
    
    if (pNodeBeforeM) {
        pNodeBeforeM->next = pHeadTmp;
    }
    pNodeM->next = pCur;
    
    return m==1 ? pHeadTmp : resultNode.next;
}

---

代码在这儿