链表OJ-----链表反转

? ? ? ? 1、链表局部反转

https://leetcode.cn/problems/reverse-linked-list-ii/

?????????

? ? ? ? 1、1初级要求：时间复杂度为O(n),空间复杂度为O(n)?

? ? ? ? 对于这个要求，我们可以想到，用一个数组，来记录反转区间中各结点的值，然后我们将数组中的值，倒着覆盖反转区间中各结点的值。?

? ? ? ? ?这个办法代码实现就比较简单了。

? ? ? ? 首先：知道反转区间链表的长度，方便开辟数组大小；然后遍历反转区间，将数放入到数组中；最后再遍历反转区间，将数组中的值，逆序放入反转区间中。

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    if (m == n) //不用翻转
        return head;
    if (head == NULL)
        return head;
    int dis1 = n - m + 1;//使用dis1，2来进行两次遍历
    int dis2 = n - m + 1;
    int* arr = (int*)malloc(sizeof(int) * dis1);
    if (arr == NULL)
        exit(-1);
    struct ListNode* cur = head;
    int tmp1 = m; //来找到第m个结点

    //找
    while (--tmp1) {
        cur = cur->next;
    }
    struct ListNode* curtmp = cur;//再次记录第m个结点，便于后续覆盖值
    //取值
    int i = 0;
    while (dis1--) {
        arr[i++] = cur->val;
        cur = cur->next;
    }

    //覆盖
    while (dis2--) {//注意数组的下标
        curtmp->val = arr[dis2];
        curtmp = curtmp->next;
    }
    return head;
}

? ? ? ? 1、2进阶要求：时间复杂度为O(n),空间复杂度为O(1)?

? ? ? ? 既然空间复杂度要求为O(1)，那我们就不能开辟数组了，只能直接将反转区间的结点指向改变了。我们就需要用“头插法”来进行改变指向。?即：将反转区间中各个结点，当作头插进反转区间链表，那么结点指向就改变了。这里就借助两个指针prev和cur指针。

????????这里就需要考虑一个问题：头结点是否在反转区间内？如果在反转区间内，最后就不能返回头结点；如果不在，最后就返回头结点。

? ? ? ? 头结点不在反转区间内

? ? ? ? 头结点在反转区间内

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    if (m == n)
        return head;

    //头结点不在反转区间
    if (m != 1) {
        int step = n - m;//记录prev走多少步，走到第n个结点
        struct ListNode* temp = head;//找第m-1个结点，记为temp
        int M = m - 1;
        while (--M) {
            temp = temp->next;
        }
        struct ListNode* prev = temp->next;//第m个
        struct ListNode* mtmp = prev;//记录第m个，方便最后改变指向
        struct ListNode* cur = prev->next;//第m+1

        //头插法
        //prev走到第n个结束
        while (step--) {
            struct ListNode* next = cur->next;//记录cur的next
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        //此时prev在第n个，cur在第n+1个
        temp->next = prev;//改变第m-1个结点的指向
        mtmp->next = cur;//改变第m个结点的指向
        return head;
    }

    //头结点在反转区间
    else {
        int step = n - m;//记录prev走多少步，走到第n个结点
        struct ListNode* temp = head;//第m个
        struct ListNode* prev = temp;//第m个
        struct ListNode* cur = prev->next;//第m+1

        //头插法
        //prev走到第n个结束
        while (step--) {
            struct ListNode* next = cur->next;//记录cur的next
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        //此时prev在第n个，cur在第n+1个
        temp->next = cur;
        return prev;
    }
    return NULL;//否则链表为空
}

? ? ? ? ?这里最重要的就是头插法，记录反转区间前后两个结点，以及改变指向。

? ? ? ? 2、链表整体反转

https://leetcode.cn/problems/reverse-linked-list/description/

? ? ? ? 有了前面局部反转的解决，那么整体反转就更简单了。就相当于一个长为x的链表，将区间[ 1,x]反转，就是全部反转了。那么这里就是包括头结点了，采用上面的方法二，可以说基本一模一样，最后头结点仍然指向最后一个结点的next（NULL），然后返回最后一个结点。

? ? ? ? 我们甚至可以在题中遍历链表得到长度，然后自己定义m = 1,n = x，然后再照搬上面的代码。不过那样不高级，我们还是自己手搓。

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)//空链表
        return NULL;
    struct ListNode* tmp = head;
    struct ListNode* prev = head;
    struct ListNode* cur = prev->next;

    //头插法
    while (cur != NULL) // prev走到最后，即cur走到NULL
    {
        struct ListNode* next = cur->next; //记录cur的next
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    tmp->next = cur; //即tmp->next = NULL
    return prev;
}

? ? ? ? 这里最重要的就是头插法！！！