1.反转链表
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。

样例
输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

迭代法:
空间复杂度分析：遍历时只有3个额外变量，所以额外的空间复杂度是 O(1)。
时间复杂度分析：只遍历一次链表，时间复杂度是 O(n)。
代码

翻转即将所有节点的next指针指向前驱节点。
由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前，不要忘记保存它的后继节点。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode*cur=head;
        ListNode*pre=NULL;
        while(cur)
        {
            //保存当前节点的后继节点 
            ListNode*ne=cur->next;
            //将当前节点指向其前驱结点完成反转 
            cur->next=pre;
            //更新前驱结点 
            pre=cur;
            //更新当前节点 
            cur=ne;
        }
        return pre;

    }
};

递归法：
首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是tail。

空间复杂度分析：总共递归 n 层，系统栈的空间复杂度是 O(n)，所以总共需要额外 O(n)的空间。
时间复杂度分析：链表中每个节点只被遍历一次，所以时间复杂度是 O(n)。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode*tail = reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return tail;

    }
};

//L是带头节点的单链表,不借助新建表
/*将头结点和后续节点断开
  遍历后续节点,执行头插到L头结点后 
 */
1.先将表L的头结点与后序断开。
2.遍历后序部分，执行头插L的头结点后

ListNode*reverList(ListNode*L)
{
    ListNode*cur=L->next;
    L->next=NULL;
    while(cur)
    {
        //保存当前节点的后继节点 
        ListNode*ne=cur->next;
        //执行头插到L的头节点后 
        cur->next=L->next;
        L->next=cur;
        //更新当前节点 
        cur=ne;
    }
    return L; 
}

2.反转链表中的某一段
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

输入：head = [5], left = 1, right = 1
输出：[5]
时间复杂度:
反转反转区间内的,循环链表,后拼接,O(n)
代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode*dummy=new ListNode(-1);
        dummy->next=head;

        ListNode*left1=dummy;
        ListNode*right1=dummy;

        //left1指针指向位置left的前一个点
        //right1指针指向位置right的点
        for(int i=0;i<right;i++)
        {
            if(i<left-1)
            {
                left1=left1->next;
            }
            right1=right1->next;
        }

        //q指向left所处位置的点,也就是反转区间的最后一个点
        ListNode*q=left1->next;
        //将右边大于right的不反转的先存下来
        ListNode*p=right1->next;  

        //反转left到right区间，pre为反转后开头节点
        ListNode*f=q;
        ListNode*pre=NULL;
        int m=0;
        while(f&&m<=right-left)
        {
            ListNode*no=f->next;
            f->next=pre;
            pre=f;
            f=no;
            m++;
        }

        // left1指针指向位置left的前一个点指向反转区间反转后的第一个点
        left1->next=pre;
        //反转区间的最后一个点连接最初右边不反转的
        q->next=p;
        return dummy->next;
    }
};