152-将链表在指定区间内反转(详细易懂)

我会带着你远行 2023-01-11 08:36 80阅读 0赞

**题目如下：**  
将一个链表m位置到n位置之间的区间反转，要求时间复杂度 O(N) 空间复杂度 O(1)  
给出的链表为1→2→3→4→5→NULL  
返回1→4→3→2→5→NULL  
注意：  
给出的 满足以下条件：  
链表长度1≤m≤n≤链表长度

## 方法1 ##

**我们找到需要翻转的区间需要4个指针**  
1、首先先额外申请一个新头结点，定义一个指针dummy指向它，这是为了防止需要翻转的是头结点。新头结点连向传入链表的头结点。  
2、定义一个指针p,p指向新头结点dummy,完成for循环后，p就是指向起始位置m结点的前驱的结点  
3、ListNode\* s = p->next; //s指向起始位置m结点  
4、ListNode\* t = s->next; //t指向起始位置m结点的next ，进入for循环，进行局部区间链表逆置  
5、for循环结束后，return dummy->next;//返回重置后的新链表

ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        
    	if(head==NULL)
    	{
        
    		return head;
    	}
    
    	ListNode* dummy = new ListNode(0);//申请一个新头结点 
    	dummy->next = head;//新头结点连向传入链表的头结点 
    	ListNode* p = dummy;//p指向新头结点 
    	for (int i = 0; i < m - 1; i++) 
    	{
        
    		p = p->next; 
    	} 
    	//此时的p指向区间链表起始位置m结点的前驱结点 
    	
    	ListNode* s = p->next; //s指向区间链表起始位置m结点 
    	ListNode* t = s->next; //t指向区间链表起始位置m结点的next 
    	
    	for (int i = m; i < n; i++)//将区间链表翻转
    	{
        
    		s->next = t->next; 
    		t->next = p->next; 
    		p->next = t; 
    		t = s->next;//t往后走 
    	} 
    	return dummy->next;//返回重置后的新链表头结点
    }

**代码运行图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 方法2（最优） ##

**方法1额外申请了一个结点，对此要进行优化，不额外申请空间**

**思路在代码注释中**

ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        
        if(head==NULL)
        {
        
            return head;
        }
        ListNode *q = head;//q指向传入链表的头结点 
    	ListNode *p = NULL;//p指向空 
        while(--m)
        {
        
        	p = q;
            q = q->next;
            --n;
        }
        //此时p是指向区间链表起始位置m结点的前驱结点位置
    	//q指向区间链表起始位置m结点 
    	
        ListNode *n = p;//用n指向p,即区间链表起始位置m结束的前驱结点位置
    	ListNode *t = q; //用t指向q，t就是区间链表翻转之后的区间链表尾结点 
        ListNode *s=NULL;
        
        while(n--)//将区间链表进行翻转 
        {
        
            s = q->next;
            q->next = n;
            n = q;
            q = s;
        }
        if (p!=NULL)//区间链表起始位置m结点不是传入链表的头结点 
        {
        
            p->next = n;//起始位置m结点的前驱结点连向区间链表翻转后区间链表的头结点 
        }
        else//区间链表起始位置m结点是传入链表的头结点 
        {
        
            head = n;//head指向区间链表翻转后区间链表的头结点 
        }
        t->next = q;//区间链表翻转后的区间链表的尾结点与q相连接 
        return head;
    }

**p,t始终不动**  
**t就是区间链表翻转之后的尾结点**  
**p就是区间链表起始位置m结点的前驱结点位置**

**代码演示图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/2387a5ca1d7f41bc94d3547a68cad837.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/bffe2218aa8d47a999327b8d26977be0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221119/5b5808a5816d417488279736931a89fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221119/656b7be83a2e4335a7e35abd4f8042e3.png