首页 > 试题广场 >

链表内指定区间反转

[编程题]链表内指定区间反转
  • 热度指数：346974 时间限制：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，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
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 回复(21)
Python3
Vivimore头像 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 回复(4)
C/C++
JordanBelfort头像 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)
C++
Spectre_头像 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)
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/C++
nbgao头像 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 回复(2)
LEarBB头像 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)
Python3
newMar头像 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 回复(2)
littleKang头像 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头像 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++
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
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)
C++
匿名的牛油头像 匿名的牛油
ListNode(-1)什么意思啊
发表于 2022-09-13 09: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)
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)
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头像 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)
C
有担当的烤冷面在找内推头像 有担当的烤冷面在找内推
// https://note.youdao.com/s/FZhxKOmP 具体图示过程
#include <stdlib.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* pre = NULL;
    struct ListNode* cur = NULL;
    struct ListNode* temp = NULL;
    int i = 0;
    newHead->next = head;
    // 找到起始位置
    pre = newHead;
    for(i = 0; i < m - 1; i++)
    {
        pre = pre->next;
    }
    cur = pre->next;  
   
    for(i = 0; i < n - m; i++)
    {
        temp = cur->next;  
        cur->next = temp->next;
        temp->next = pre->next;
        pre->next = temp;
    }
    return newHead->next;
}

发表于 2023-08-04 15:59:27 回复(0)
Python3
Winnyting头像 Winnyting
类：
    定义区间反转链表函数：
        初始化虚拟链表res
        定义res下一个节点为头节点
        将res虚拟链表赋值给pre
        实链表头节点赋值给cur
        遍历第一个节点到区间上边界：
            实链表赋值给pre
            cur指向下一个节点
        遍历反转区间：
            cur的下一节点值赋值给临时变量temp
            temp的下一个节点赋值给cur的下一个节点
            pre的下一节点赋值给remp下一节点
            temp赋值给pre下一个节点
        返回 虚拟链表res下一节点
            
            
            
        
发表于 2023-06-04 22:08:43 回复(0)
C
阿金要努力头像 阿金要努力 
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)
LinuX18头像 LinuX18 
class Solution {
public:
    
    ListNode *reverseBetween(ListNode *head, int m, int n) 
    {     
        ListNode *fake = new ListNode(0);
        fake->next = head;
        ListNode *p = fake;
        
        for(int i=0;i<m-1;i++)
            p = p->next;
        ListNode *firstTail = p,*secondTail = p->next;
        
        ListNode *pre = nullptr,*node = secondTail;
        for(int i=0;i<n-m+1;i++)
         {
            ListNode *temp = node->next;
            node->next = pre;
            pre = node;
            node = temp;
         }
         firstTail->next = pre;
         secondTail->next = node;
        
        return fake->next;
    }
};

发表于 2017-07-09 18:06:05 回复(0)
提交观点

问题信息

链表
难度：
492条回答 31536浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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