【LeetCode】BM1 反转链表、NC21 链表内指定区间反转

梦里梦外; 2024-03-25 10:01 85阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

## BM1 反转链表 ##

描述：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度O(n) 。

如当输入链表\{1,2,3\}时，

经反转后，原链表变为\{3,2,1\}，所以对应的输出为\{3,2,1\}。

以上转换过程如下图所示：

![7e3cda22a8aac921429407f70557dc5d.png][]

示例：

![535bc53415694ff7b3413fe7829dcc47.png][]

思路：

初始化：3个指针  
1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr  
2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head  
3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存  
接下来，循环执行以下三个操作  
1）nex = cur->next, 保存作用  
2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点  
3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点  
循环条件，当然是cur != nullptr  
循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点

代码：

struct ListNode* ReverseList(struct ListNode* pHead ) {
        // write code here
    
        struct ListNode*prep=NULL;
        struct ListNode*cur1=pHead;
        struct ListNode*cur2;
        while(cur1)
        {
            cur2=cur1->next;
            cur1->next=prep;
            prep=cur1;
            cur1=cur2;
        }
        return prep;
    }

## NC21 链表内指定区间反转 ##

[链表内指定区间反转\_牛客题霸\_牛客网][Link 1]

题目描述：

描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。  
例如：  
给出的链表为 1→2→3→4→5→NULL, m=2,n=4,  
返回1→4→3→2→5→NULL.

数据范围： 0<size≤1000，0<m≤n≤size，链表中每个节点的值满足∣val∣≤1000

要求：时间复杂度 O(n) ，空间复杂度O(n)

进阶：时间复杂度 O(n)，空间复杂度 O(1)

示例1：

![5d914fd07e434287821889ac51ee9156.png][]

思路：

先找到m的位置然后从进行翻转就可以，看我注释

*  step 1：我们可以在链表前加一个表头，后续返回时去掉就好了，因为如果要从链表头的位置开始反转，在多了一个表头的情况下就能保证第一个节点永远不会反转，不会到后面去。
 *  step 2：使用两个指针，一个指向当前节点，一个指向前序节点。
 *  step 3：依次遍历链表，到第m个的位置。
 *  step 4：对于从m到n这些个位置的节点，依次断掉指向后续的指针，反转指针方向。
 *  step 5：返回时去掉我们添加的表头。

代码：

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
        // write code here
        struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
        newhead->next=head;
        struct ListNode*cur1=head;
        struct ListNode*prep=newhead;
        for(int i=1;i<m;i++)
        {//找到m的位置
            cur1=cur1->next;
            prep=prep->next;
        }
        for(int i=m;i<n;i++)
        {
            struct ListNode* cur2=cur1->next;
            cur1->next=cur2->next;//防止找不到cur2后面的那个节点
            cur2->next=prep->next;//cur2一定在翻转部分的最前面。
            //翻转后在前面的节点一定在prep的后一个节点
            prep->next=cur2;
        }
        return newhead->next;
    }

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/899c1c837156459cadc69d1c51076fe6.png
[7e3cda22a8aac921429407f70557dc5d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/195b8fc9739d4a3aa0afc92ea82ae265.png
[535bc53415694ff7b3413fe7829dcc47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/27d9a5298cb04b84a11f02a1193be4fc.png
[Link 1]: https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=196&tqId=37060&ru=/exam/oj#:~:text=%E4%B8%8B%E4%B8%80%E9%A2%98-,NC21%20%E9%93%BE%E8%A1%A8%E5%86%85%E6%8C%87%E5%AE%9A%E5%8C%BA%E9%97%B4%E5%8F%8D%E8%BD%AC,-%E9%A2%98%E7%9B%AE
[5d914fd07e434287821889ac51ee9156.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9f77b403af21440b9788e97f474c0494.png