【LeetCode】 reverse-linked-list-ii

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M 热度指数：20029

本题知识点： 链表 leetcode

 算法知识视频讲解

题目描述

将一个链表m位置到n位置之间的区间反转，要求使用原地算法，并且在一次扫描之内完成反转。

例如：

给出的链表为1->2->3->4->5->NULL, m = 2 ，n = 4,

返回1->4->3->2->5->NULL.

注意：

给出的m，n满足以下条件：

1 ≤ m ≤ n ≤ 链表长度

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

For example:
Given1->2->3->4->5->NULL, m = 2 and n = 4,

return1->4->3->2->5->NULL.

Note: 
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

示例1

输入

复制

{1,2,3,4,5},2,4

输出

复制

{1,4,3,2,5}

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode L =ListNode(0);
        L.next=head;
        ListNode* p=&L;
        ListNode* q=head;
        for(int i=1;i<m;i++){
            p=q;
            q=q->next;
        }
        for(int i=0;i<(n-m);i++){
            ListNode* t=q->next;
            q->next=t->next;
            t->next=p->next;
             p->next=t;
        }
        return L.next;
    }
};