首页 > 试题广场 >

链表内指定区间反转

[编程题]链表内指定区间反转

热度指数：445075 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：链表长度 $0 < size \le 1000$ ， $0 < m \le n \le size$ ，链表中每个节点的值满足 $|val| \le 1000$

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

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

示例1

输入

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

输出

{1,4,3,2,5}

示例2

输入

{5},1,1

输出

{5}

示例3

输入

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

输出

{4,3,2,1}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

小牛写代码

#include <stdlib.h>

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {

// write code here

struct ListNode* pre = head;

struct ListNode* cur = NULL;

for(int i = 1; i < (m - 1); i++)

{

pre = pre->next;

}

cur = pre->next;

for(int i = 0; i < (n-m); i++)

{

struct ListNode* next = cur->next;

cur->next = next->next;

next->next = pre->next;

pre->next = next;

}

return head;

}

发表于 2025-09-20 16:36:22 回复(0)

乐观的小辣鸡在改简历

本质是寻找到第一个要交换的结点，然后将目前结点连接到下一个结点，而next结点实行头插，插到pre的后面，pre指针不动，只负责头插的头，移动next和now结点

/**

* 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

struct ListNode* hd = (struct ListNode*)malloc(sizeof(struct ListNode));

hd->next = head;

struct ListNode* pre = hd;

struct ListNode* now = NULL;

struct ListNode* nex = NULL;

for (int i = 1; i < m; i++) {

pre = pre->next;

}

now = pre->next;

//到这里抵达反转起始位置

// 执行n-m次反转操作

int c = n - m;

while(c --){

nex = now->next;

now->next = nex->next;

nex->next = pre->next;

pre->next = nex;

}

struct ListNode* result = hd->next;

free(hd);

return result;

}

发表于 2025-09-09 14:07:11 回复(0)

覃世想

想的比较乱

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @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 == NULL||m>=n){

return head;

}

struct ListNode* next = head;

struct ListNode* nextnext = next->next;

struct ListNode* temp = NULL;

struct ListNode* headd = next;

struct ListNode* start = next;

for(int i=1;next!=NULL;i++){

if(i==m-1){

start = next;

headd = next->next;

nextnext = next->next->next;

}else if(i>=m&&i<n){

temp = nextnext->next;

nextnext->next = headd;

headd = nextnext;

nextnext = temp;

}else if(i==n){

if(m==1){

start->next = nextnext;

head = headd;

}else{

start->next->next = nextnext;

start->next = headd;

}

next = next->next;

}

return head;

}

发表于 2025-09-05 00:42:28 回复(0)

wander_ing

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

// 定位区间前驱节点和起始节点
struct ListNode* prev = NULL;
struct ListNode* curr = head;
for (int i = 1; i < m; i++) {
prev = curr;
curr = curr->next;
if (curr == NULL) return head; // 防止越界
}
struct ListNode* start = curr; // 区间起始节点
struct ListNode* end = start;

// 定位区间结束节点
for (int i = m; i < n; i++) {
end = end->next;
if (end == NULL) return head; // 防止越界
}
struct ListNode* after = end->next; // 保存区间后的节点

// 分离区间（只断开区间末尾）
end->next = NULL;

// 逆转区间
struct ListNode* rev_prev = NULL;
struct ListNode* rev_curr = start;
struct ListNode* rev_next = NULL;
while (rev_curr != NULL) {
rev_next = rev_curr->next;
rev_curr->next = rev_prev;
rev_prev = rev_curr;
rev_curr = rev_next;
}
struct ListNode* new_head = rev_prev; // 逆转后的区间头

// 重新连接链表
if (prev != NULL) {
prev->next = new_head;
} else {
head = new_head; // 若从第一个节点开始逆转，更新链表头
}
start->next = after; // 原区间头（现区间尾）连接到后续节点

return head;

}

思路：先找到区间的节点，然后保存左区间的前节点和右区间的后节点，然后把区间的链表进行逆转，然后重新连接

发表于 2025-08-05 17:23:52 回复(0)

牛客712087098号

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {

    struct ListNode* pm_prev = NULL;
    struct ListNode* pm = NULL;
    struct ListNode* pn = NULL;
    struct ListNode* pn_next = NULL;
    struct ListNode* p_last = NULL;
    struct ListNode* p_next = NULL;
    struct ListNode* p_cur = NULL;
    int i = 0;

    if (!head) {
        return NULL;
    }

    if (m > n) {
        return NULL;
    }

    p_cur = head;
    for (i=1; p_cur; i++) {       
        p_next = p_cur->next; 
        if (pm) {
            // reverse
            if (i > m) {
                p_cur->next = p_last;
            }
        }

        if (i == m) {
            pm = p_cur;
            pm_prev = p_last; // maybe NULL
        }

        if (i == n) {
            pn = p_cur;
            pn_next = p_next; // maybe NULL
        }


        if (pn) {
            //fond n, end
            pm->next = pn_next;
            if (pm_prev) {
                pm_prev->next = pn;
            } else {
                pm->next = pn_next;
                return pn;
            }

            return head;
        }


        p_last = p_cur;
        p_cur = p_next;
    }

    return head;
}

发表于 2025-03-25 09:47:43 回复(0)

爱抖振的滑模ctrl

具体思路就是把一个链表的每一个元素头插法插在新的一个链表上就完成链表的反转。所以只需要找到开始反转的位置，然后依次把该元素及之后需要反转元素头插法插在新的链表里，就完成部分链表的反转。然后再把反转后的链表接回原来的链表中，并输出。

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {

// write code here

if (m == n) return head;

struct ListNode *p;

struct ListNode *q;

struct ListNode *head1 = (struct ListNode *)malloc(sizeof(struct ListNode));

struct ListNode *head2 = (struct ListNode *)malloc(sizeof(struct ListNode));

head1->val = 0;

head1->next = NULL;

head2->val = 0;

head2->next = head;

p = head2;

q = head2->next;

for (int i=0; i<m-1 ; i++)

{

p = p->next;

q = q->next;

}

for (int i=0 ; i<=n-m ; i++)

{

p->next = q->next;

q->next = head1->next;

head1->next = q;

q = p->next;

}

p->next = head1->next;

for (int i = 0; i<=n-m; i++)

{

head1 = head1->next;

}

head1->next = q;

head1 = NULL;

head = head2->next;

free(head2);

free(head1);

return head;

}

发表于 2025-03-17 15:28:01 回复(0)

苏杭下小雨

/**
 * 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
    struct ListNode*start=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*last=(struct ListNode*)malloc(sizeof(struct ListNode));
    start->next=head;
    struct ListNode*p=head;
    while(p->next!=NULL)
    {
        p=p->next;
    }
    last->next=p->next;
    p->next=last;
    struct ListNode*pre=start;
    struct ListNode*first=NULL;
    struct ListNode*second=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*third=(struct ListNode*)malloc(sizeof(struct ListNode));
    for(int i=0;i<m-1;i++)
    {
        pre=pre->next;
    }
    second=pre->next;
    struct ListNode*q=second;
    struct ListNode*rear=pre;
    for(int i=m-1;i<n+1;i++)
    {
        rear=rear->next;
    }
    while(second!=rear)
    {
        third=second->next;
        second->next=first;
        first=second;
        second=third;
    }
    pre->next=first;
    q->next=rear;
    struct ListNode*l=start;
    while(l->next->next!=NULL)
    {
        l=l->next;
    }
    l->next=NULL;
    if(m==1)
    {
        head=first;
    }
    return head;
}

感觉官方视频那个视频有点看不懂，我直接把所需要的部分链表翻转再接回原链表，但是这样做，需要考虑m=1的特殊情况，不知道也采用这种暴力思路的码友们有没有更好的思路来合并这种特殊情况

发表于 2025-03-14 20:22:50 回复(0)

爱得扣

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)

小白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)

鱼也爱下雨

用数组感觉要简单。

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)

杨歪杰刷题日常

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)

牛客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)

牛客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)

躺平又起来了的菜鸡很自来熟

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)

不存在的神秘人

试错了好多次才写出来

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)

一个优雅的程序猿

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)

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)

提交观点

问题信息

链表

难度：

68条回答 2340收藏 35616浏览

通过挑战的用户

查看代码

满洲里有象&

2023-03-11 00:48:38
雷雷雷子

2023-03-07 20:47:18
nephen

2023-03-06 23:24:07
hao12138

2023-03-05 16:07:19
宾客斯的美酒

2023-02-21 10:56:31

链表内指定区间反转

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题