【小白爬Leetcode】1.2反转链表Ⅱ

题目

反转一个单链表。

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

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

难度:
$\color{#FF7D00}{medium}$medium

心得：
这道题的难度在于特殊情况：
1.m==n：
这是最简单的情况，表示不用反转，直接返回return head；

2.m=1:
这是次简单的情况，但容易搞错。只需要考虑反转之后的新片段的尾部指向原链表第n+1个节点，并return反转片段的头部；

3.其他情况:
最一般的情况，反转之后的新片段需要完成两件事与原链表缝合：原链表的第m-1个节点指向新片段的头部，新片段的尾部指向原链表的第n+1个节点；此外还要return原链表的第1个节点。

思路一：先生成逆序片段，再拼接回原来的链表

这是一个很自然的想法：把问题简化成两个：1.先生成逆序片段：相当于一个easy等级的题目；2.再把生成的片段拼接回原链表，缺点是：需要用到多达6个指针。

使用六个指针的迭代解法：

相比于1.1反转整个链表用到3个指针：

        ListNode* head;//参数列表里初始化
        ListNode* pre = NULL;
        ListNode* next = NULL;

这里新增了3个指针：

        ListNode* front = NULL; //指向第m-1个节点
        ListNode* new_end = NULL; //表示反转片段的尾部节点
        ListNode* begin = NULL;  //表示原链表的第一个节点，如果m==1那么这个指针始终是NULL

这三种情况的图解思路：

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* pre = NULL;
        ListNode* next = NULL;
        ListNode* front = NULL;
        ListNode* new_end = NULL;
        ListNode* begin = NULL;
        int count = 1;

        //如果m==n，不用反转，直接返回原链表
        if(m==n)
        {
            return head;
        }
        //记录下原链表的第一个值，作为m!=1时的函数返回值
        else if(count == 1)
        {begin = head;}
        
        //遍历1到n节点
        while(count<n+1)
        {
            //记录m-1个节点，循环结束后指向反转片段的头部
            if(count==m-1){front = head;}
            //如果没到第m个节点，直接向后遍历
            if(count<m ){head = head->next;}
            //到了第一m个节点，开始反转
            else
            {
            //new_end记录反转片段的尾部，循环结束后指向n+1个节点
            if(count == m){new_end = head;}
            //反转过程
            next = head->next;
            head->next = pre;
            pre = head;
            head = next;
            }
            count++;
        }

        // if(head!=NULL)
        // {
        //     count++;
        // }


        //新链表尾部接原来n+1的节点（即第n次循环后得到的head，如果n是原链表最后一个节点则head == NULL）
        new_end->next = head;

        //如果m!=1，则原链表m-1的节点接反转片段的头部（即第n次循环后得到的pre），并返回begin（原链表的第一个节点）
        if(m>1)
        {
        front->next = pre;
        return begin;
        }
        //如果m==1，则直接返回反转片段的头部（即第n次循环后得到的pre）即可
        else
        {return pre;}
        
    }
};

复杂度分析：

·时间复杂度： 假设 n是列表的长度，时间复杂度是 O(n)。
·空间复杂度： O(1)

结果如下：
这一看就很假嘛哈哈哈哈；

思路二 每一步把下一个节点挪到缺口的最前面

$\color{#FF3030}{这个思路是在评论区里看到的}$这个思路是在评论区里看到的，特点如下：
1.在原数组前设置了一个头节点以应对m=1的情况；
2.只用了三个指针 p、item、tail ;
3.每一步的结果都是一个完整链接的链表，循环完成之后不必再把片段和原链表链接起来。

比如原来有1->2->3->4->5->NULL, m=2, n=4
那么首先把3挪到2的前面，变成了：1->3->2->4->5->NULL，
再把4挪到3的前面，变成了：1->4->3->2->5->NULL，
大功告成。

大概实现过程如下：

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if(m == n)
        return head; // 不用管的情况
    struct ListNode h = {0, head}; //添加第0个节点,处理m=1的情况
    struct ListNode* p = &h;
    struct ListNode* tail;
    for(int i = 1; i <= n; i++)
        if(i < m) // 如果m!=1的话，p指向第m-1个节点位置，若m==1，那么p指向第0个节点
            p = p->next;
        else if(i == m) // tail指向第第m个节点，这个节点反转后处在反转部分的最后一个
            tail = p->next;
        else { //每次将tail后面一个节点拿出来，放在p后面
            struct ListNode* item = tail->next;  //item是要往前挤的节点
            tail->next = tail->next->next; //item往前移的话，就少了一个坑，当然是用tail的下下个填上啦
            item->next = p->next; //tail和第m-1个节点(也就是)
            p->next = item;
        }
    return h.next;
}

结果如下：