leadcode的Hot100系列--206. 反转链表
这里使用两种方式,
一个是直接从头往后遍历 -------> 迭代
一个是从最后一个往前遍历 -----> 递归
迭代
定义三个变量:ppre pnext pnow
ppre表示当前节点的前一个地址,pnext表示当前节点的下一个地址,pnow表示当前节点的地址。
反转的核心:就是把 pnow的next指针,指向 ppre
因为反转之后,pnow的next原来的值会丢,所以在反转之前,要用pnext把原来的值保存一下。
反转之后,要处理下一个节点,而本节点就是下一个节点的前一个节点,所以用ppre把当前节点地址保存一下。
struct listnode* reverselist(struct listnode* head){ struct listnode *pstpre = null; struct listnode *pstnow = head; struct listnode *pstnext = null; while (null != pstnow) { pstnext = pstnow->next; // 先保存一下当前节点的next指针 pstnow->next = pstpre; // 做反转 pstpre = pstnow; // 更新pstpre指针 pstnow = pstnext; // 继续做下一个节点的反转 } return pstpre; }
递归
递归的话,不太好理解,先上代码,看着代码来理解:
struct listnode* reverselist(struct listnode* head){ struct listhode *pstnewhead = null; if (head == null || head->next == null) // 如果链表为空,或者是最末端节点,则直接返回当前节点地址 { return head; } else { pstnewhead = reverselist(head->next); // 返回新链表头节点 head->next->next = head; // 这里完成反转 head->next = null; return pstnewhead; } }
递归写法的关键是:head->next->next = head 这句代码中,
head 是谁,head->next 是谁,head->next->next 又是谁!
可以从后往前理解,假设有三个节点,为 1 -> 2 -> 3,
最后一次:当head为节点2时,入参为传入节点3,节点3的next为null,返回节点3的地址。
此时:head指向节点2,pstnewhead指向节点3,
-----> 得到:head->next 指向节点3,head->next->next 就相当于节点3的next,
所以:执行完 "head->next->next = head"之后,就相当于把节点3的next指向了节点2,完成一个反转。
而节点2的next指针已经没用了(原本节点2的next指向了节点3),直接指向null。
上面部分实现了节点3与节点2的反转,并此时pstnewhead指向了节点3。
再继续。
上面返回pstnewhead为节点3的地址,此时入参的head为1(因为之前head为节点2,返回调用者的时候,是head->next为节点2,所以这里调用者为节点1),
所以,head->next为2,head->next->next 就相当于是节点2的next,所以执行完 "head->next->next = head"之后,就相当于把节点2的next指向了节点1。
而节点1原来的next没用了(原本节点1的next指向了节点2),直接指向null,这里就相当于是链表尾部。
然后返回pstnewhead。
其实这里pstnewhead只赋值过一次,之后从未改变,一直指向了最一开始的节点3。
推荐阅读
-
leadcode的Hot100系列--155. 最小栈
-
leadcode的Hot100系列--64. 最小路径和--权值最小的动态规划
-
leadcode的Hot100系列--136. 只出现一次的数字
-
leadcode的Hot100系列--461. 汉明距离
-
leadcode的Hot100系列--62. 不同路径--简单的动态规划
-
leadcode的Hot100系列--347. 前 K 个高频元素--hash表+直接选择排序
-
leadcode的Hot100系列--78. 子集--回溯
-
leadcode的Hot100系列--617. 合并二叉树
-
leadcode的Hot100系列--二叉树创建和遍历
-
leadcode的Hot100系列--226. 翻转二叉树