题目

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

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

示例:

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

解析

反转整个链表的升级版，难度不大，麻烦的是如何处理m=1和m>1的情况
可以设置一个哑节点dummy在开头

代码

  1. class Solution {
  2. public:
  3.     //双指针法，pre先走m-1步到达位置m的前驱节点，pre不动，然后令cur等于pre->next也就是位置m的起始节点（不变），将[m+1,n]这段链表由前至后的插入到位置m的前面，也就是pre的后面
  4.     //换句话说：我们每次循环就是将cur的next节点插入到pre的后面，这样插了n-m次后，就完成反转了
  5.     ListNode* reverseBetween(ListNode* head, int m, int n) {
  6.         //设置哑节点的好处：在m=1时，我们也有前驱节点，也可以将cur的next节点依次插入到pre的后面
  7.         ListNode *dummy=new ListNode(-1);
  8.         dummy->next=head;
  9.         ListNode *pre=dummy;
  10.         //找到m的前驱节点
  11.         for(int i=1;i<m;++i)pre=pre->next;
  12.         ListNode *cur=pre->next;
  13.         for(int i=m;i<n;++i){//每次循环将nxt节点插入到pre的后面
  14.             ListNode *nxt=cur->next;
  15.             //cur将nxt节点后面的链表连接起来
  16.             cur->next=nxt->next;
  17.             //将nxt插入到pre后面
  18.             nxt->next=pre->next;
  19.             pre->next=nxt;
  20.         }
  21.         return dummy->next;
  22.     }
  23. };