55-将单链表原地逆置（三种方法）

迈不过友情╰ 2022-12-24 13:59 154阅读 0赞

**方法1：用三个指针实现单链表（有头结点）的逆置**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

void Reverse(HeadList *head)
    {
        
    	if(head==NULL||head->next==NULL||head->next->next==NULL)
    	return ;
    	HeadList *s=NULL;
    	HeadList *p=head->next;
    	HeadList *q=p->next;
    	while(p!=NULL)
    	{
        
    		p->next=s;
    		s=p;
    		p=q;
    		if(q!=NULL)
    		{
        
    			q=q->next;
    		}
    	}
    	head->next=s;//头结点指向尾结点
    }

**方法2：用两个指针实现单链表（有头结点）的逆置 ，利用head->next代替上面代码的s指针**

void Reverse(HeadList *head)
    {
        
    	
    	if(head==NULL||head->next==NULL||head->next->next==NULL)
    	return ;
    	HeadList *p=head->next;
    	HeadList *q=p->next;
    	head->next=NULL;
    	while(p!=NULL)
    	{
        
    		p->next=head->next;
    		head->next=p;
    		p=q;
    		if(q!=NULL)
    		{
        
    			q=q->next;
    		}
    	}
    }

**方法3：使用递归方法将单链表逆置（无头结点）**  
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点  
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点  
同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转  
当递归函数全部出栈后，链表反转完成。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

ListNode* reverseList(ListNode *head)//单链表逆置
    {
        
    	if(head == NULL || head->next == NULL)
    	{
        
    		return head;
    	}
    	ListNode *newHead = reverseList(head->next);//递归入栈
    	head->next->next = head;//反转指向线路
    	head->next = NULL;//切断原来的指向线路
    	return newHead;//返回新的头结点
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/36f19d50154a45e18516ad553aacb364.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/633e97caef8f45fa88ef606224b5c7ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/01cb8ef30af04671b03ca1f2a9a2fe88.png