LeetCode 92. 反转链表 II（Reverse Linked List II）

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

1输入: 1->2->3->4->5->NULL, m = 2, n = 4
2输出: 1->4->3->2->5->NULL

解题思路

本题类似于反转链表的做法，但不同的是只反转中间的一段节点，所以在反转完一段链表后，应重新拼接到原链表对应位置中间。具体步骤为：

• 首先找到反转链表的首尾节点，若首节点不是链表头结点，还要同时保存首节点的前一个节点，以便反转完后的拼接
• 然后按照反转链表的做法维护三个指针，从头到尾一遍遍历调整指针，这样遍历到尾节点时正好反转完指定链表段
• 最后将原来的首节点next指针指向段后节点，若首节点不是链表头结点，还要讲首节点前一个节点的next指针指向原来的尾节点

代码

1 1 /**
2 2  * Definition for singly-linked list.
3 3  * struct ListNode {
4 4  *     int val;
5 5  *     ListNode *next;
6 6  *     ListNode(int x) : val(x), next(NULL) {}
7 7  * };
8 8  */
9 9 class Solution {
1010 public:
1111     ListNode* reverseBetween(ListNode* head, int m, int n) {
1212         ListNode *left = head, *first, *pre;
1313         int step = m;
1414         while(step - 2 > 0){
1515             left = left->next;
1616             step--;
1717         }
1818         if(m > 1) first = pre = left->next;
1919         else first = pre = head;
2020         step = n - m;
2121         if(step > 0){
2222             ListNode *now = pre->next;
2323             ListNode *next = now->next;
2424             while(step-- > 0){
2525                 now->next = pre;
2626                 pre = now;
2727                 now = next;
2828                 if(next) next = now->next;
2929             }
3030             if(m > 1) left->next = pre;
3131             first->next = now;
3232         }
3333         if(m > 1) return head;
3434         else return pre;
3535     }
3636 };