反转链表 II

题目

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

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

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

题解:

翻转链表记录当前结点的前一节点pre，临时保存当前结点的下一节点t，然后当前结点的next为pre，pre=当前结点，当前结点=t，这样就达到了翻转的效果。

此题由于不是从头到尾直接翻转，而是只翻转从m->n这些节点，需要注意细节，分情况讨论。

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //当m==n,说明不用翻转,直接返回
        if(m==n)
            return head;

        //当前节点
        ListNode* tmp = head;
        //记录m的前一个节点
        ListNode* pre_m = NULL;
        // 记录翻转时所用到的前一个节点
        ListNode* pre = NULL;
        // 记录m节点
        ListNode* t_m =NULL;
        //遍历的节点数
        int i=1;

        while(true)
        {
            if(i<m)
            {
                pre_m = tmp;
                tmp = tmp->next;
            }
            else if(i==m)
            {
                pre = tmp;
                t_m = tmp;
                tmp = tmp->next;
            }
            else if(i>m&&i<n)
            {
                //翻转指针
                ListNode* t = tmp->next;
                tmp->next = pre;
                pre = tmp;
                tmp = t;
            }
            else if(i==n)
            {
                //当pre_m为空说明hh头节点应该指向tmp,否则就是pre_m节点xx指向tmp
                if(pre_m==NULL)
                    head = tmp;
                else
                    pre_m->next = tmp;

                ListNode* t = tmp->next;
                tmp->next = pre;
                t_m->next = t;
                break;
            }

            i++;
        }

        return head;
    }