数据结构|LeetCode(206. 反转链表)

目录

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

前言 小伙伴们大家好,今天小编为大家带来一篇力扣上与链表有关的一个题目:反转链表。
如下图所示,我们需要将正好回文的链表的所有元素做一个反转,如下图所示:
数据结构|LeetCode(206. 反转链表)
文章图片

题目 正如上面提到的一样,题目如下所示:
数据结构|LeetCode(206. 反转链表)
文章图片


规律 规律:我们发现,其实反转也就是相当于将源链表的 “箭头” 的方向正好全部反过来。
那么既然是相当于将原链表的 “箭头” 的方向反过来,那么怎样做才能将箭头反过来呢?
这里我们提供了如下所示这样一种思路。
思路 首先,我们需要三个指针,然后第一个指针 n1 指向原链表之前的节点(第一次该节点是不存在的),第二个指针 n2 指向原链表的头节点,第三个指针 n3 指向原链表头指针的下一个节点。如下图所示:
数据结构|LeetCode(206. 反转链表)
文章图片

然后最主要的一步,我们需要将 n2 指针的 next 指向 n1,也就是反转箭头。这里我们主要的思想就是这一步骤了。如下图所示:
数据结构|LeetCode(206. 反转链表)
文章图片

之后就是三个指针同时往后移动一位,这里其实 n3 节点,就是用来记录下一个节点,然后在移动的时候就必须用到了。否则我们只用两个指针的话,下一个节点的查找就会变得很麻烦,所以这里不论从哪方面考虑,我们都是需要用三个指针实现的, 如下图所示:
数据结构|LeetCode(206. 反转链表)
文章图片

但是这里其实 n3 指针是需要做判断的,如果 n3 节点为空的话,是不能继续往后移动的。然后当 n2 节点表示的位置为空时,此时 n1 节点就是最后的新链表的头节点,如下图所示:
数据结构|LeetCode(206. 反转链表)
文章图片

我们看到,此时 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. 反转链表)】数据结构|LeetCode(206. 反转链表)
文章图片

    推荐阅读