【牛客算法BM2】链表内指定区间反转网站首页 技术杂谈

【牛客算法BM2】链表内指定区间反转

悲伤的猪大肠9 2024-07-04 11:18:03

简介【牛客算法BM2】链表内指定区间反转

你好，欢迎来到我的博客！作为一名程序员，我经常刷LeetCode题目来提升自己的编程能力。在我的博客里，我会分享一些我自己做过的题目和解题思路，希望能够帮助到大家。今天，我想和大家分享一道挑战性较高的题目，让我们一起来挑战一下吧！作者也是在学习的过程中刷到有意思的题目就会选择与大家分享，并且提供较优解，关于力扣的文章全部放在博客，如果大家喜欢记得支持作者。?

题目难度：中等

在这里插入图片描述

示例1：

输入：{1,2,3,4,5},2,4

返回值：{1,4,3,2,5}

示例2：

输入：{5},1,1

返回值：{5}

解题思路?

先遍历到反转区域的前一个位置，这里如果第一个位置就是链表头会出现麻烦的判空问题，所以定义一个头结点，使head连接到头结点，定义一个prev指向头结点，cur指向头结点的下一个位置，遍历到反转区域的前一个位置之后，将prev定格将prev定格在这里，cur继续向下走，每次将cur指向后面第二个next，再将cur的后一位头插到prev后，直到执行n-m次

下面方法要做的操作说大白话就是
例如链表为 1 -》2 -》3 -》4 -》5 需求反转2 - 4 范围内的节点
①：先找到要反转节点的上一个节点也就是 1。ListNode pre = 1
②：开始进行循环反转从反转的起点开始:ListNode temp = 2
第一次循环:
（1) 先暂存3 ListNode next = temp.next;
（2) 让 2 指向 4 temp.next = next.next
（3) 让 3 指向 2 即指向要反转节点的头部pre.next; next.next = pre.next
（4) 让 1 指向 3 pre.next = next;
（5) 第一次循环结果 1 -》3 -》2 -》4 -》5

示例

在这里插入图片描述

代码实现⭐

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    if(head==NULL||head->next==NULL)
        return head;
     struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
     phead->next = head;	//为了防止prev判空问题直接定义一个头结点让prev指向头节点
     struct ListNode* prev,*cur,*temp;
     prev = phead;
     cur = phead->next;
    for(int i=0;i<m-1;i++)	//找到反转区域的前一个位置，将prev定格在这里，cur继续向下走
    {
        prev = prev->next;
        cur = cur->next;
    }
    for(int i=0;i<n-m;i++)	//每次将cur指向后两位next，再将cur的后一位头插到prev后
    {
        temp = cur->next;					
        cur->next = temp->next;
        temp->next = prev->next;
        prev->next = temp;
    }
    
    return phead->next;			//返回头结点下一位
}