反转链表的四种方法_链表反转

目录

1.第一种方法：原地反转。

2.第二种方法：利用头插法进行反转链表。

3. 第三种方法：利用迭代法进行反转链表。

 4.第四种方法：利用递归法进行反转链表。

5.应用。

---

        当我们学习链表之后，就要学习一些链表的操作，而反转链表是我们必备技能，这里总结了链表反转的几种方法，希望可以有用。

1.第一种方法：原地反转

  我们先定义一个结构体。

typedef struct stu{
    int id;
    struct stu*next;
}STU;

        原地反转是通过两个指针对链表进行调整，从而使得链表达到反转的效果，我们可以通过下面的模型来整个链表的操作过程。

为什么需要两个指针呢？

因为在操作的过程中需要取出中间的一个额，这样就会导致后面的数据丢失，当我们有两个指针的时候就可以避免这种情况发生。

注意：在这里我们统一让链表头的不存入数据。

   1.我们首先定义它的头指针为phead，然后我们就可以对我们需要的两个两个指针进行定义。

STU*beg=phead->next;

STU*end=phead->next->next;

   2.当我们定义好这些所需要的指针后，就要进行对数据原地反转的操作了。 

 这个就是我们接下来的思维路线，形象的可以把这四步操作总结为“连”，“掉”，“接”，“移”。

1. 连：我们将beg->next=end->next，这样就会避免后面的数据丢失。
2. 掉：接下来将end放在所有数据的前面，就是end->next=head->next。
3. 连：这个时候就要把连移动的数据放在头指针的后面，即head->next=end。
4. 移：最后就是要把下一个需要定义的数据往下移动一位，便是end=beg->next。

//下面便是这四步代码

        beg->next=end->next;
        end->next=Pheadlist->next;
        Pheadlist->next=end;
        end=beg->next;

最后我们得到的结果就是

 3.我们很容易的把一个数据给反转了过来，接下来就是要反转后面的所有，我们用的思路都死一样的。

    任然是要使用我们的四步走 ，从而将第三个数据放在最前面。

效果如下：

 

         最后便是将最后一个数据当在最前面，依然熟练的运用前面的方法就行。~~

4.我们可以利用这个方法解决这个反转的问题，但是我们在什么时候停止呢，很容易看出，最后一个就是beg->next==NULL,或者end==时便结束整个循环。

下面就是整个代码

//原地反转链表
STU*Rollback1(STU*Pheadlist)
{
	STU*beg=Pheadlist->next;
	STU*end=Pheadlist->next->next;
	while(end!=NULL){
		beg->next=end->next;
		end->next=Pheadlist->next;
		Pheadlist->next=end;
		end=beg->next;
	}
	return Pheadlist;
}	

以上便是原地反转的所有操作。 

2.第二种方法：利用头插法进行反转链表。

        头插法相信大家都很熟悉了，接下来我们就利用头插法的思想，进行反转链表，同样的我们还是需要两个指针，这样防止后面的数据丢失。

STU*p,*q;

p=phead->next;

q=p->next;

话不多说，我们任然利用图像进行分析。

 1.我们首先将前面的所有东西断开，然后进行后面数据的插入。

phead->next=NULL;

        通过图片我们可以看出是利用四步走，将链表反转。

1. 利用q将后面的数据连接起来。
2. 将取出来的数据接到之前链的前面，也就是p->next=head->next;
3.  让头指针接上取出来的数据。
4. 数据进行后移。

这四步就是我们整个的核心，接下来是这个步骤所需要的代码。

	    q=p->next;
		p->next=phead->next;
		phead->next=p;
		p=q;

 2.接下来看看后面的图形

         从图中我们可以发现，依然运用了上面的四步，然后使得后面的a3接到了后面。

3.我们利用头插法四步走将链表一一反转，那我们后面是需要怎样操作才可以将这个循环停止呢，很简单，当最后一个数据的下一个数据为空时则停止，便是q==NULL，或者p==NULL；

后面我们写一下这个代码。

STU*Headback(STU*phead)
{
	STU*p=phead->next;
	phead->next=NULL;
	STU*q;
	while(p!=NULL){
		q=p->next;
		p->next=phead->next;
		phead->next=p;
		p=q;
	}
	return phead;
}

以上便是头插法反转的所有操作。 

3. 第三种方法：利用迭代法进行反转链表。

        咱们先了解一下迭代是什么意思：迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

迭代就是这样的，有点那懂，但是我们还是可以了解其中的一些信息，我们要将迭代得到的结果会作为下一次迭代的初始值。

那么接下来看看迭代在链表中怎么应用。

依旧上图。

         我们首先需要三个指针，一个是当前节点cur，一个是当前节点的上一个prev，一个是当前节点的next。

    STU*prev=NULL,*next;
    STU*cur=phead->next;

接下来就是一步步转化。

1.我们需要让next指向cur的下一个。

2.把cur的下一个指向上一个。

3.然后就是转化，把上一个指向当前，把当前指向下一个。

我们很清楚的可以了解到，迭代法也是运用四个步骤。

下面就是具体代码。

        next=cur->next;
		cur->next=prev;
		prev=cur;
		cur=next;

那么我们怎么结束这个过程呢，很简单就是让最后一个的下一个不为空，便是cur不为空。

因为我们的头指针都是不存数据的，所以现在我们需要把头指针接到这个新排好的链表上面去。

下边把所有的代码显示出来。

STU*Iterate(STU*phead)
{
	STU*prev=NULL,*next;
	STU*cur=phead->next;
	while(cur!=NULL){
		next=cur->next;
		cur->next=prev;
		prev=cur;
		cur=next;
	}
	phead->next=prev;
	return phead;
}

以上便是迭代法反转的所有操作。

 4.第四种方法：利用递归法进行反转链表。

递归相信大家都是很熟悉的，所以也就不一一讲解了，就只是说一下需要注意的几个点。

首先我们的代码都是头指针不含有数据的，所以我们需要两个函数。

STU* Reverselist(STU*phead)
{
	STU*head=phead->next;
	head=Reverse(head);
	phead->next=head;
	return phead;
}

这个就是我们需要转换的一个函数，里面的Reserve便是递归函数所有的代码。

STU*Reverse(STU*head)
{
	if(head==NULL||head->next==NULL)
	return head;
	STU*newhead=Reverse(head->next);
	head->next->next=head;
	head->next=NULL;
	return newhead;
}

这个就是递归的方法。

5.应用。

 这个是力扣上面的一个题，可以利用上面的方法求解。

下面展示一下迭代的方法。

struct ListNode* reverseList(struct ListNode* head){
        struct ListNode*prev=NULL,*next;
	    struct ListNode*cur=head;
        while(cur!=NULL){
            next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
}

        以上便是总结的所有方法了。