数据结构|LeetCode（206. 反转链表）链表|leetcode|数据结构|c语言

目录

前言
题目
规律
思路
代码实现

前言小伙伴们大家好，今天小编为大家带来一篇力扣上与链表有关的一个题目：反转链表。
如下图所示，我们需要将正好回文的链表的所有元素做一个反转，如下图所示：

文章图片

题目正如上面提到的一样，题目如下所示：

文章图片

规律规律：我们发现，其实反转也就是相当于将源链表的 “箭头” 的方向正好全部反过来。
那么既然是相当于将原链表的 “箭头” 的方向反过来，那么怎样做才能将箭头反过来呢？
这里我们提供了如下所示这样一种思路。
思路首先，我们需要三个指针，然后第一个指针 n1 指向原链表之前的节点（第一次该节点是不存在的），第二个指针 n2 指向原链表的头节点，第三个指针 n3 指向原链表头指针的下一个节点。如下图所示：

文章图片

然后最主要的一步，我们需要将 n2 指针的 next 指向 n1，也就是反转箭头。这里我们主要的思想就是这一步骤了。如下图所示：

文章图片

之后就是三个指针同时往后移动一位，这里其实 n3 节点，就是用来记录下一个节点，然后在移动的时候就必须用到了。否则我们只用两个指针的话，下一个节点的查找就会变得很麻烦，所以这里不论从哪方面考虑，我们都是需要用三个指针实现的，如下图所示：

文章图片

但是这里其实 n3 指针是需要做判断的，如果 n3 节点为空的话，是不能继续往后移动的。然后当 n2 节点表示的位置为空时，此时 n1 节点就是最后的新链表的头节点，如下图所示：

文章图片

我们看到，此时 n1 即表示反转之后的新链表的头节点。
代码实现

struct ListNode* reverseList(struct ListNode* head){ struct ListNode*n1=NULL; struct ListNode*n2=head; if(head==NULL) return NULL; struct ListNode*n3=head->next; while(n2) { //核心 n2->next=n1; //移动 n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; }

好的，那么本文到此就结束啦！如有问题，还请指正呀！
【数据结构|LeetCode（206. 反转链表）】