剑指 Offer 24. 反转链表【递归、迭代】
题目描述
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
1 | 输入: 1->2->3->4->5->NULL |
限制:
1 | 0 <= 节点个数 <= 5000 |
解题思路
方法一:迭代
迭代法:定义一个伪头部,遍历head链表,使用头插法插入到伪头部链表中,最后返回虚拟头部的next指针即可。
代码实现
1 | public ListNode reverseList(ListNode head) { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
方法二:递归
递归调用,修改结点的指针转向。
代码实现
1 | public ListNode reverseList2(ListNode head) { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) //递归调用栈使用。
资源
剑指 Offer 24. 反转链表【递归、迭代】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.