【剑指Offer】反转链表
程序员文章站
2022-06-30 20:43:33
题目描述 输入一个链表,反转链表后,输出新链表的表头。 解法1 可以使用三个辅助指针pHead, last,next pHead记录当前节点,last记录上一个节点,next记录下一个节点 首先使用next保存当前节点的下一个节点,然后将当前节点的下一个节点指向last,实现反转 如下图所示 实现代 ......
题目描述
输入一个链表,反转链表后,输出新链表的表头。
解法1
可以使用三个辅助指针phead, last,next
phead记录当前节点,last记录上一个节点,next记录下一个节点
首先使用next保存当前节点的下一个节点,然后将当前节点的下一个节点指向last,实现反转
如下图所示
实现代码
public listnode reverselist(listnode phead) { listnode last = null, next = null; while(phead != null){ next = phead.next; phead.next = last; last = phead; phead = next; } return last; }
解法2
解法1是将链表按照从头到尾的顺序反转的
可以使用递归,通过不断递归深入,实现先从链表的尾节点开始反转
然后通过递归的回溯实现按照从尾到头的顺序反转每个节点
如下图所示
实现代码
public listnode reverselist2(listnode phead) { if(phead == null || phead.next == null) return phead; listnode node = reverselist2(phead.next); phead.next.next = phead; phead.next = null; return node; }
更多算法题目的完整描述,ac代码,以及解题思路可以查看github仓库algorithm
推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer13:数组[奇数,偶数],奇数偶数相对位置不变。
-
剑指offer第二天
-
剑指offer JZ31 整数中1出现的次数 Python 解