本文共 1920 字，大约阅读时间需要 6 分钟。

一天一道LeetCode

本系列文章已全部上传至我的github，地址：

欢迎大家关注我的新浪微博，

欢迎转载，转载请注明出处

（一）题目

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:

Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:

Given m, n satisfy the following condition:

1 ≤ m ≤ n ≤ length of list.

（二）解题

题目大意：反转链表中从m到n的部分链表。

注：反转链表需要注意链表断裂问题。

解题思路：首先，依次遍历链表记录第m-1个节点startPre，和第m个节点start；

然后从m到n，进行反转链表，记录pre和p，新建一个临时temp = p，p->next=pre，pre=p，p=temp；就完成反转链表了 最后，记录第n个节点end和第n+1和节点endNext。 做好如上工作之后，进行最后把三部分连接起来的工作

此时需要分为两类

1、m=1时，这时候头结点是end，只需要将start的next指向endNext，然后返回end即可 2、m！=1时，这时候头节点还是head，就需要吧中间部分连起来，返回head即可。 具体见代码：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* reverseBetween(ListNode* head, int m, int n) {        ListNode* p = head;        ListNode* startPre;//第m-·个节点        ListNode* start;//第m个节点        ListNode* end;//第n个节点        ListNode* endNext;//第n+1个节点        if(m==1) {
  //m=1是第0个节点为NULL            startPre = NULL;            start = p;        }        else {            for(int i = 0 ; i < m-2 ; i++)            {                p = p->next;            }            startPre = p;            start = p->next;        }        //以上找到startPre和start        //开始反转链表        ListNode* pre = start;//记录p的前一个节点        p = start->next;        for(int i = m ; i < n ; i++)        {            ListNode* temp = p->next;//记录p的下一个节点，防止断裂            p->next = pre;            pre = p;            p = temp;        }        //找到end和endNext        end = pre;        endNext = p;        if(startPre == NULL) {
  //即m=1的情况，这时候头节点为end            start->next =endNext;            return end;        }        else{
  //即m!=1的情况，头节点仍为head            startPre->next = end;            start->next =endNext;            return head;        }        return head;    }};