首页 > 试题广场 >

链表内指定区间反转

[编程题]链表内指定区间反转
  • 热度指数：397623 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 ，空间复杂度 。
例如：
给出的链表为 , ,
返回 .

数据范围： 链表长度 ，，链表中每个节点的值满足
要求：时间复杂度  ，空间复杂度
进阶：时间复杂度 ，空间复杂度
示例1

输入

{1,2,3,4,5},2,4

输出

{1,4,3,2,5}
示例2

输入

{5},1,1

输出

{5}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
C
爱得扣头像 爱得扣
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    struct ListNode* temp_head = head;
    struct ListNode* temp = NULL;
    struct ListNode* back = NULL;
    struct ListNode* n_next = NULL;
    struct ListNode* m_back = NULL;
    struct ListNode* m_node = NULL;
    struct ListNode* n_node = NULL;
    if (n > m) {
        for (int i = 1; i < n; i++) {
            if (i == m) {
                m_back = back;
                m_node = head;
            }
            back = head;
            head = head->next;
            if (i == n - 1) {
                n_node = head;
                n_next = head->next;
            }
        }
    }  
    else
        return head;  //n==m直接返回
    back = NULL;
    struct ListNode* m_same_node = m_node;
    //将范围内的节点反转
    while (m_node != n_next) {
        temp = m_node->next;
        m_node->next = back;
        back = m_node;
        m_node = temp;
    }
    m_same_node->next = n_next;   //将m处节点与n节点下一位连接
    //判断m是否从头结点开始，若不是则将n节点与m节点上一位连接后返回
    if (m_back) {
        m_back->next = n_node;
        return temp_head;
    }
    //判断m为头结点后直接返回n节点即可
    return n_node;
}
发表于 2024-11-10 14:44:37 回复(0)
C
小白0080头像 小白0080 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode *reverseBetween(struct ListNode *head, int m, int n)
{
    // write code here
    //增加一个头结点方便操作
    struct ListNode * L=(struct ListNode*)malloc(sizeof(struct ListNode));
    L->next=head;
    struct ListNode *pre = L; // 记录弟m的前一个结点
    struct ListNode *end = head; // 记录弟n的后一个结点
    struct ListNode *p1 = head;//弟m个结点
    struct ListNode *p2;
    struct ListNode *p3;
    int i = 1;
    while (p1 && i < m)//找到弟m个结点
    {
        /* code */
        pre = p1;
        p1 = p1->next;
        i++;
    }
    // printf("%d\n",p1->val);
    i = 0;
    while (end && i < n)//找到n的下一个结点
    {
        end = end->next;
        i++;
    }
    //  printf("%d\n",end->val);
    //进行区间翻转
    struct ListNode *begin=p1;
    p2 = p1->next;
    p3 = p2;
    i = m;
    while (p2 && i < n)
    {
        p3 = p3->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        i++;
    }
    begin->next=end;//把原本第一个结点接到弟n个结点之后
    pre->next=p1;//反转后的弟n个结点连接弟m的前一个
    return L->next;
}

发表于 2024-10-20 11:49:32 回复(0)
C
鱼也爱下雨头像 鱼也爱下雨
用数组感觉要简单。
struct ListNode* reverseBetween(struct ListNode* head, int m, int n )
 {
    // write code here
    struct ListNode* move = head, *tmp1 = NULL, *tmp2 = NULL, *tmp3 = NULL;
    int num = 0;
   
    int i = 0,j = 0, th = 0, arr[100] = {0};
    while (move)
    {
        i++;
        if (i >= m && i <= n )
        {
            arr[i] = move->val;
        }
        move = move->next;
    }
    move = head; i = 0;
   while (move)
    {
        i++;
        if (i >= m && i <=n && j <= (n-m)+1)
        move->val = arr[n-j++];
        move = move->next;
       
    }

  return head;

}
发表于 2024-09-22 21:06:29 回复(0)
C
杨歪杰刷题日常头像 杨歪杰刷题日常 
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if (head == NULL || m == n) return head;

    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* pre = &dummy;

    for (int i = 1; i < m; i++) {
        pre = pre->next;
    }

    struct ListNode* start = pre->next;
    struct ListNode* then = start->next;

    for (int i = 0; i < n - m; i++) {
        start->next = then->next;
        then->next = pre->next;
        pre->next = then;
        then = start->next;
    }

    return dummy.next;
}

发表于 2024-08-26 23:49:43 回复(1)
C
牛客183275086号头像 牛客183275086号
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->next = head;
    struct ListNode* prev = temp;
    for(int i = 0; i < m - 1; i++)
    {
        prev = prev->next;
    }
    struct ListNode* start = prev->next;
    struct ListNode* end = start;
    for(int i = m; i <= n; i++)
    {
        end = end->next;
    }
    prev->next = NULL;
    struct ListNode* current = start;
    struct ListNode* next = NULL;
    while(current != end)
    {
        next = current->next;
        current->next = prev->next;
        prev->next = current;
        current = next;
    }
    start->next = end;

    return temp->next;
}
发表于 2024-07-11 21:58:40 回复(0)
C
牛客577829019号头像 牛客577829019号 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    struct ListNode *prev = NULL;
    struct ListNode *next = NULL;
    struct ListNode *phead = head;
    struct ListNode *reverseBegin = NULL;
    struct ListNode *reverseEnd = NULL;
    int i = 1;

    if (NULL == head || NULL == head->next || m >= n)
    {
        return head;
    }

    while(NULL != head)
    {
        if (i < m)
        {
            /* 记录翻转链表开始的地方 */
            reverseBegin = head;
            head = head->next;
        }
        /* 翻转链表结束后 */
        else if (i > n)
        {
            head = head->next;
        }
        else {
            if (i == m)
            {
                /* 翻转链表结束的地方是原翻转链表开头 */
                reverseEnd = head;
            }

            /* 对需要翻转的节点进行翻转 */
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;

            /* 翻转链表最后一个节点时拼接前后的链表 */
            if (i == n)
            {
                /* 考虑翻转链表从第一个结点开始 */
                if (1 == m)
                {
                    phead = prev;
                    /* 考虑翻转链表后面没有结点的情况 */
                    if (NULL != head)
                    {
                        reverseEnd->next = head;
                    }
                }
                else {
                reverseBegin->next = prev;
                reverseEnd->next = head;
                }
            }
        }
        i++;
    }

    return phead;
}

编辑于 2024-04-13 22:08:40 回复(0)
C
躺平又起来了的菜鸡很自来熟头像 躺平又起来了的菜鸡很自来熟 
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    if (head->next == NULL || head == NULL) {
        return head;
    } else if (m == n) {
        return head;
    }
    struct ListNode* temp = NULL;
    struct ListNode* prehead1 = NULL;
    struct ListNode* prehead2 = NULL;
    struct ListNode* prehead = NULL;
    int i = 0, j = 0;
    prehead = head;
    while (i < m - 1) {
        prehead1 = head;
        head = head->next;
        i++;
    }
    while (i < n) {
        temp = head->next;
        head->next = prehead2;
        prehead2 = head;
        head = temp;
        i++;
    }
    if (prehead1 == NULL) {
        prehead1 = prehead2;
        while (prehead2->next != NULL) {
            prehead2 = prehead2->next;
        }
        prehead2->next = temp;
        return prehead1;
    } else {
        prehead1->next = prehead2;
    }
    while (prehead2->next != NULL) {
        prehead2 = prehead2->next;
    }
    prehead2->next = temp;
    return prehead;

}

发表于 2024-03-30 21:48:41 回复(0)
C
不存在的神秘人头像 不存在的神秘人
试错了好多次才写出来
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    if(m==n) return head;
    struct ListNode* p,*q,*r,*t;
    struct ListNode *head2 = (struct ListNode*)malloc(sizeof(head));
    r=head2;
    int index=m;
    head2->next=head;
    for(int i=0;i<m-1;i++)
    head2=head2->next;
    p=head2->next;
    t=head2->next;
    head2->next=NULL;
    while (index<=n&&p!=NULL) {
        q=p;
        p=p->next;
        q->next=head2->next;
        head2->next=q;
        index++;
    }
    t->next=p;
    return r->next;
}
编辑于 2024-03-20 17:00:56 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct ListNode* GetListNode(struct ListNode* head, int m) {
    struct ListNode *p1;
    p1 = head;
    while(--m>0) 
        p1 = p1->next;
    return p1;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    struct ListNode *res, *buffer;
    if(head == NULL || head->next == NULL || m==n)
        return head;
    if(m==1) {
        int i,j;
        for(i=0;i<n/2;i++) {
            j = GetListNode(head,i+1)->val;
            GetListNode(head,i+1)->val = GetListNode(head,n-i)->val;
            GetListNode(head,n-i)->val = j;
        }
        return head;
    }
    res = reverseBetween(head, m, n-1);
    buffer = GetListNode(head,n);
    GetListNode(head,n-1)->next = buffer->next; 
    buffer->next = GetListNode(head,m);
    GetListNode(head,m-1)->next = buffer;
    return res;
}

编辑于 2024-03-13 20:09:42 回复(0)
C
zxy4头像 zxy4
struct ListNode* reverseBetween( struct ListNode* head, int m, int n) {
    struct ListNode* prev = head;
    struct ListNode* front = head;
    struct ListNode* cur = head;
    struct ListNode* next = head;
    int a = m - 1;
    int b = n - 1;
    while (a--) {
        prev = prev->next;
    }
    while (b--) {
        cur = cur->next;
    }
    while (front && front->next != prev) {
        front = front->next;
    }
    next = cur->next;
    struct ListNode* temp1 = prev;
    struct ListNode* pre = NULL;
    while (prev != next) {
        struct ListNode* temp = prev->next;
        prev->next = pre;
        pre = prev;
        prev = temp;
    }
    if (front != NULL) {
        temp1->next = next;
        front->next = cur;
    } else {
        temp1->next = next;
        head = cur;
    }
    return head;
}
编辑于 2024-02-11 18:24:26 回复(0)
C
小汐儿头像 小汐儿
struct ListNode* reverse(struct ListNode* head,struct ListNode* tail)
 {
      struct ListNode* phead = NULL;
      struct ListNode* prev = head;
      struct ListNode* cur = head->next;
      struct ListNode* ptail = tail->next;
      while(prev != tail)
      {
         prev->next = phead;
         phead = prev;
         prev = cur;
         if(cur)
         {
            cur = cur->next;
         }
      }
      prev->next = phead;
      head->next = ptail;
      return prev;
 }
struct ListNode* reverseBetween(struct ListNode* head, int m, int n )
{
    struct ListNode* pa = (struct ListNode*)malloc(sizeof(struct ListNode));
    pa->next = head;
    if(m == n)
    {
        return head;
    }
    else
    {
        struct ListNode* phead = head;
        struct ListNode* pphead = head;
        struct ListNode* cur1 = pa;
        struct ListNode* cur2 = pa;
        int i = 1;
        int j = 1;
        while(i < m)
        {
           cur1 = phead;
           phead = phead->next;
           i++;
        }
        while(j < n)
        {
           cur2 = pphead;
           pphead = pphead->next;
           j++;
        }
        if(m < n)
        {
           cur1->next =  reverse(phead,pphead);
        }
        else
        {
           cur2->next = reverse(pphead,phead);
        }
    }
    return pa->next;
}
发表于 2024-01-24 16:51:45 回复(0)
C
牛客770548236号头像 牛客770548236号 
#include <stdlib.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) 
{
    typedef struct ListNode list;
    //如果是从首节点开始反转，则没有上一个节点需要记录，所以需要创建一个首节点的上节点来保证程序正确。
    list* empty =(list*)malloc(sizeof(list));
    empty->val =0;
    empty->next =head;
    int i =0;
    list* p1 =empty;
    for(i=0;i<m-1;i++)
    {
        p1=p1->next;
    }
    //记录开始节点
    list* start = p1->next;
    list* new_node =start;
    list* p2 =NULL;
    for(i = m-1;i<n;i++)
    {
        list* tmp = new_node->next;
        new_node->next =p2;
        p2 =new_node;
        new_node =tmp;
    }
    //链表反转结束，开始区间反转
    p1->next =p2;
    start->next = new_node;
    //如果是从头反转，头节点不再是输入的节点
    list* new_head =empty->next;
    free(empty);
    return new_head;
}

编辑于 2024-01-08 11:33:14 回复(0)
C
衣舞佳月头像 衣舞佳月
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    if (!head || m == n) return head;
    struct ListNode* cur = malloc(sizeof(struct ListNode));
    cur->val = -1;
    cur->next = head;
    struct ListNode* res = cur;
    for (int i = 0; i < m - 1; i++) {
        res = res->next;
    }
    struct ListNode* now = res->next;
    struct ListNode* next;
    for (int i = 0; i < n - m; i++) {
        next = now->next;//=next->next
        now->next = next->next;
        next->next = res->next;
        res->next = next;//=now->next
    }
    return cur->next;
}
发表于 2023-12-14 22:31:56 回复(0)
C
月银_头像 月银_ 
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    int x = m;//记录起始位置
    int c = n-m;//记录反转次数
    if(c<=0 || head==NULL)//当不反转或空表时直接返回
    {
        return head;
    }
    
    struct ListNode* p = head;  //用于记录区间前一个元素
    struct ListNode* first = head;  //用于记录区间第一个元素
    if(x>1)//当区间外存在前一个元素时
    {
        while(m-2)//将p移动到区间前一个元素位置
        {
            p = p->next;
            m--;
        }
        first = p->next;//移动到区间第一个位置
    }
    
    struct ListNode* left = first;        //记录左边的元素（目标元素）
    struct ListNode* right = first->next; //记录右边的元素（移动元素）
    while(c)//反转次数
    {
        first->next = right->next;//使用区间第一个元素的next，记录移动元素下个元素的地址
        right->next = left; //反向连接
        left = right; //目标元素向右移动
        right = first->next; //移动元素向右移动
        c--;
    }
    
    if(x<=1)//当区间外不存在前一个元素时，头节点为left
    {
        return left;
    }else {//存在前一个元素时，头节点为head
        p->next = left;//前一个元素的next指向区间最后一个元素
        return head;
    }
    
}

编辑于 2023-12-14 09:44:25 回复(0)
C
A202302282044461头像 A202302282044461
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    if(head == NULL || head->next==NULL ||m==n)
        return head;
    struct ListNode *new_head = (struct ListNode *)malloc(sizeof(struct ListNode));     //申请一个节点
    if( new_head == NULL)   //判断是否申请成功
        return NULL;
    new_head->next = head;//定义为新的头结点

    struct ListNode *pHead = NULL;
    struct ListNode *temp = NULL;
    struct ListNode *pTail = NULL;
    int i;

    head = new_head;
    for (i=0; i<m-1; i++) {     //找到需要翻转节点的头一个节点
        head = head->next;
    }
    pHead = head;   //记录该节点
    pTail = head->next; //记录尾节点，两边翻转完成后需要将后面未翻转的链表连接起来
    head = head->next->next;//头插法反转链表
    for (i=0; i<n-m; i++) {
        temp = head;    
        head = head->next;
        temp->next = pHead->next;
        pHead->next = temp;
    }
    pTail->next = head;

    return new_head->next;
}
发表于 2023-08-28 15:12:06 回复(0)
C
无名珠头像 无名珠 
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {

    struct ListNode phead; //设置虚拟头结点
    phead.next = head;

    struct ListNode *next = NULL;  //反转的下一个节点
    struct ListNode *prior = NULL; //反转的前一个节点

    struct ListNode *start = &phead; //反转链表第一个节点
    struct ListNode *end = NULL;    //反转链表最后一个节点

    struct ListNode *left = NULL;   //反转链表前的一个节点
    struct ListNode *right = NULL;  //反转链表后的一个节点

    int i = 0;

    for (i=0; i<m-1; ++i) //找到链表反转的前一个节点
    {
        start = start->next; //start的起始值：并不是整个链表的第一个节点
    }

    head = right = left = start->next; //链表反转的第一个节点

    for (i=m; i<n; ++i) //找到链表反转的最后一个节点
    {
        right = right->next;
    }

    end = right->next; //反转链表结束后的节点

    right->next = NULL; //将反转部分断开

    while (head!=NULL)
    {
        next = head->next;  //存储下一个节点
        head->next = prior; //反转
        prior = head;       //存储前一个节点
        head = next;        //移到下一个节点
    }

    start->next = right; //将断开的链表接上
    left->next = end;    //将断开的链表接上

    return phead.next;
}

编辑于 2023-12-17 16:11:42 回复(1)
提交观点

问题信息

链表
难度：
61条回答 33628浏览

热门推荐

通过挑战的用户

查看代码

相关试题

链表内指定区间反转

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号