首页 > 试题广场 >

链表内指定区间反转

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

热度指数：444742 时间限制：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，点此查看相关信息

算法知识视频讲解

查看答案及解析

黄色变白色

用栈来翻转链表

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(head == nullptr || m <= 0 || n <= 0)
            return head;
        
        ListNode *newHead = new ListNode(-1);
        newHead->next = head;
        ListNode *pm = newHead;
        
        for(int i = 1; i < m;++i)
            pm = pm->next;

        stack<ListNode*> lSt;
        ListNode* preNode = pm;
        
        pm = pm->next;
        for(int i = 0; i <= n-m;++i)
        {
            lSt.push(pm);
            pm = pm->next;
        }

        ListNode *lastNode = pm;
        
        while(!lSt.empty())
        {
            preNode->next = lSt.top();
            preNode = preNode->next;
            lSt.pop();
        }
        
        preNode->next = lastNode;
        head = newHead->next;
        delete newHead;
        return head;
    }
};

发表于 2020-09-06 15:42:18 回复(1)

更多回答

Java

詆調壹點

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		ListNode preStart = dummy;
		ListNode start = head;
		for (int i = 1; i < m; i ++ ) {
			preStart = start;
			start = start.next;
		}
		// reverse
		for (int i = 0; i < n - m; i ++ ) {
			ListNode temp = start.next;
			start.next = temp.next;
			temp.next = preStart.next;
			preStart.next = temp;
		}
		return dummy.next;
	}
}

发表于 2016-12-03 00:25:32 回复(22)

Python3

Vivimore

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        res = ListNode(-1)
        res.next = head
        pre = res
        cur = head
        for i in range(1, m):
            pre = cur
            cur = cur.next
        for i in range(m, n):
            temp = cur.next
            cur.next = temp.next
            temp.next = pre.next
            pre.next = temp
        return res.next

好难想明白啊

发表于 2022-05-13 19:44:10 回复(5)

C/C++

JordanBelfort

//1.将原链表分为三部分，m之前，m到n直接，n之后，并切断其联系
//2.将m,n之间链表反转
//3.将三部分重新连接
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode* dummy = new ListNode(-1);
    	dummy->next = head;
        ListNode* pNode = dummy;
    	ListNode* ftail = pNode,*rhead = NULL, *rtail = NULL, *res = NULL;
        for (int i = 0; i < m - 1; i++)
        	ftail = ftail->next;
        rhead = ftail->next;
        ftail->next = NULL;
        ListNode* prev = NULL, *pcur = rhead, *pnext = rhead->next;
        for (int i = m; i <= n;i++) {
            pcur->next = prev;
            prev = pcur;
            pcur = pnext;
            pnext = pnext->next;
        }
        res = pcur;
        ftail->next = prev;
        rhead->next = res;
        ListNode* phead = dummy->next;
        dummy->next = NULL;
        delete dummy;
    	return phead;
    }
};

编辑于 2017-03-10 14:05:54 回复(3)

Java

键盘都敲坏了.

下面方法要做的操作说大白话就是
* 例如链表为 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
以此类推即可得解

public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode dum = new ListNode(0);
        dum.next = head;
        ListNode pre = dum; 

        for(int i = 1; i < m; i++){
            pre = pre.next; // 找到m的上一个节点
        }
        head = pre.next; // 从m的位置开始进行交换
        ListNode next;   // 用于暂存遍历节点的后继节点
        for(int i = m; i < n; i++){
            // 暂存遍历节点的下一个节点
            next = head.next;
            // 让当前节点指向 后继节点的后继节点
            head.next = next.next;
            // 让后继节点指向反转元素的首位
            next.next = pre.next;
            // 让m的上一个节点 指向 此后继节点
            pre.next = next;
        }
        return dum.next;
    }

发表于 2022-10-24 21:08:19 回复(5)

C++

Spectre_

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // 时间复杂度O(N)，空间复杂度O(1)
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy;
        for (int i = 1; i < m; ++i) pre = pre->next;
        ListNode *cur = pre->next, *nex;
        for (int i = m; i < n; ++i) {
            nex = cur->next;
            cur->next = nex->next;
            nex->next = pre->next;
            pre->next = nex;
        }
        return dummy->next;
    }
};

发表于 2022-09-28 17:08:28 回复(2)

C/C++

nbgao

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode L = ListNode(0);
        L.next = head;
        ListNode *p = &L;
        ListNode *q = head;
        for(int i=1;i<m;i++)
        {
        	p = q;
        	q = q->next;
		}
		for(int i=0;i<n-m;i++)
		{
			ListNode *t = q->next;
			q->next = t->next;
			t->next = p->next;
			p->next = t;
		}
		return L.next;
    }
};

发表于 2017-09-12 00:52:31 回复(3)

Python3

newMar

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        if m == n:
            return head

        lis = [None, head]
        while lis[-1].next:
            lis.append(lis[-1].next)
        while m <= n:
            lis[m].val, lis[n].val = lis[n].val, lis[m].val
            m += 1
            n -= 1
        return head

编辑于 2023-09-08 19:58:00 回复(3)

LEarBB

大致画个图：分为1-m m-n n+1-end 用指针记录分界结点，逆序后链接即可。【注意判NULL】

ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(head == NULL || head->next == NULL) return head;
        
    	ListNode *q = NULL, *p = head;
    	for (int i = 0; i < m - 1; i++)
    	{
    		q = p;
    		p = p->next;
    	}
    
    	// p此时指向第m个结点
    	ListNode *end = p;
    	ListNode *pPre = p, *nxt = NULL;
    	p = p->next;
    
    	// m->n之间的结点逆序
    	for (int i = m + 1; i <= n; ++i)
    	{
    		nxt = p->next;
    		p->next = pPre;
    		pPre = p;
    		p = nxt;
    	}
        // p指向原链表中第n个结点的下一个结点
        // end表示逆序子链表的尾结点
    	end->next = p;
        
        // pPre指向的是逆序后的子链表头
        // q指向的是第m个结点前一个结点 注意有可能是NULL
    	if (q)
    		q->next = pPre;	// 不是NULL 链接起来即可
    	else
    		head = pPre;	// 是NULL 头结点即为子链表头
    
    	return head;
    }

发表于 2016-04-22 00:34:31 回复(2)

littleKang

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        for(int i=1;i<m;i++) {
            p = p.next;
        }
        
        ListNode pm = p.next;
       
        for(int i=m;i<n;i++) {
            ListNode temp = pm.next;
            pm.next = temp.next;
            temp.next = p.next;
            p.next = temp;
        }
        
        return dummy.next;
    }
}

发表于 2016-03-15 15:55:52 回复(0)

Python3

ling201909271034152

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        newHead = ListNode(0) # 附加一个头结点，使得空链表和非空链表得到统一
        newHead.next = head
        p = newHead # 反转部分的前一个指针，可以看做是反转部分的头结点
        cur = p.next
        i = 1
        while i < n:
            if i < m:
                p = cur
                cur = p.next
            else:
                # 永远想着把当前结点的后继变成反转部分的前驱，当前结点永远是反转部分的最后一个结点
                pre = cur.next
                cur.next = pre.next
                pre.next = p.next
                p.next = pre
            i += 1
        return newHead.next

发表于 2023-02-03 16:28:31 回复(0)

C++

匿名的牛油

ListNode(-1)什么意思啊

发表于 2022-09-13 09:49:49 回复(0)

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode dummy(0);
    dummy.next = head;
    
    ListNode* p = &dummy;
    for (int i = 0; i < m - 1; ++i)
      p = p->next;
    
    stack<ListNode*> stk;
    ListNode* q = p->next;
    for (int i = 0; i < n - m + 1; ++i) {
      stk.emplace(q);
      q = q->next;
    }
    
    while (not stk.empty()) {
      p = p->next = stk.top();
      stk.pop();
    }
    
    p->next = q;
    return dummy.next;
  }
};

发表于 2021-08-14 09:28:07 回复(0)

阿金要努力

struct ListNode *reverseBetween(struct ListNode *head, int m, int n) 
{
    struct ListNode *newnode = malloc(sizeof(struct ListNode));
    newnode->next=head;
    struct ListNode* cur=newnode,*prev=newnode;
    for(int i=0;i<m;i++)
    {
        prev=cur;
        cur=cur->next;
    }
    for(int i=0;i<n-m;i++)
    {
        struct ListNode* next=cur->next;
        cur->next=next->next;
        next->next=prev->next;
        prev->next=next;
    }
    return newnode->next;
}

发表于 2022-07-01 19:49:49 回复(0)

元气の悟空

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        vector<int> a;
        int i;
        ListNode *p;
        for(p=head;p;a.push_back(p->val),p=p->next);
        reverse(a.begin()+m-1,a.begin()+n);
        for(i=0,p=head;p;p->val=a[i],i++,p=p->next);
        return head;
    }
};

发表于 2016-08-13 15:47:37 回复(1)

Java

牛客839384289号

public ListNode reverseBetween (ListNode head, int m, int n) {
    // write code here
    ListNode pre=new ListNode(0) ,p1=pre;
    pre.next=head;
    for(int i=1;i<m;i++){
        p1=p1.next;
    }
    ListNode p2=p1.next ,temp=p1.next;
    for(int i=m;i<=n;i++){
        ListNode node=p2.next;
        p2.next=p1.next;
        p1.next=p2;
        p2=node;
    }
    temp.next=p2;
    return pre.next;
}

发表于 2024-06-02 13:43:15 回复(0)

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)

Python3

Winnyting

类：

定义区间反转链表函数：

初始化虚拟链表res

定义res下一个节点为头节点

将res虚拟链表赋值给pre

实链表头节点赋值给cur

遍历第一个节点到区间上边界：

实链表赋值给pre

cur指向下一个节点

遍历反转区间：

cur的下一节点值赋值给临时变量temp

temp的下一个节点赋值给cur的下一个节点

temp赋值给pre下一个节点

返回虚拟链表res下一节点

发表于 2023-06-04 22:08:43 回复(0)

Python3

我想吃饭呜呜呜

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        temp = head
        res = []
        length = 0
        while temp is not None:
            length += 1
            res.append(temp.val)
            temp = temp.next
        res1 = []
        if n<length:
            res1 = res[:m-1]+res[m-1:n][::-1]+res[n:]
        else:
            res1 = res[:m-1]+res[m-1:n][::-1]
        temp = head
        i = 0
        while temp is not None:
            temp.val = res1[i]
            temp = temp.next
            i += 1
        return head

发表于 2023-03-11 13:37:28 回复(0)

Java

倔强小头

// 用一个列表添加head数据，用一个列表添加反转数据
// 然后把反转数据一一赋值到第一个列表上 就OK了
public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m==n) return head;
        ArrayList<Integer> list=new ArrayList<>();
        ArrayList<Integer> list1=new ArrayList<>();
        ListNode current=head;
        while (current!=null){
            list.add(current.val);
            current=current.next;
        }
        for (int i = m-1; i < n; i++) {
            list1.add(list.get(i));
        }
        Collections.reverse(list1);
        int index=0;
        for (int i = m-1; i < n; i++) {
            list.set(i,list1.get(index++));
        }
        current=head;
        int i=0;
        while (current!=null){
            current.val=list.get(i);
            i++;
            current=current.next;
        }
        return head;
    }

发表于 2021-11-29 12:00:15 回复(3)

secndf

/**
 * Step1: 先创建一个“哨兵”节点，再找到索引m的前驱节点p
 * Step2: 将m～n之间的节点采用头插法，插入到索引m的前驱节点后面
 * Step3: 剩余的节点插入到头插链表的尾部
 */
ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (head == nullptr)
            return head;
        ListNode *p = new ListNode(-1), *root = p, *item, *q;
        p->next = head;
        int x = m;
        while (--x > 0){
            p = p->next;
        }
        bool first = true;
        head = p->next;
        p->next = nullptr;
        while (m++ <= n){
            item = head;
            if (first){
                q = item;
                first = false;
            }
            head = head->next;
            item->next = p->next;
            p->next = item;
        }
        if (q != nullptr)
            q->next = head;
        return root->next;
    }

发表于 2020-03-19 23:24:57 回复(0)

提交观点

问题信息

链表

难度：

585条回答 2340收藏 35586浏览

通过挑战的用户

查看代码

满洲里有象&

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，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题