剑指 Offer 24. 反转链表【递归、迭代】

题目描述

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制:

1
0 <= 节点个数 <= 5000

解题思路

方法一:迭代

迭代法:定义一个伪头部,遍历head链表,使用头插法插入到伪头部链表中,最后返回虚拟头部的next指针即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = null;
while (head != null) {
ListNode next = head.next;
head.next = dummyHead.next;
dummyHead.next = head;
head = next;
}
return dummyHead.next;
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1)

方法二:递归

递归调用,修改结点的指针转向。

代码实现

1
2
3
4
5
6
7
8
9
public ListNode reverseList2(ListNode head) {
if (head == null||head.next==null) {
return head;
}
ListNode newHead = reverseList2(head.next);
head.next.next=head;//指针转向
head.next=null;
return newHead;
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(n) //递归调用栈使用。

资源

  1. https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
  2. https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/fan-zhuan-lian-biao-by-leetcode-solution-jvs5/

剑指 Offer 24. 反转链表【递归、迭代】

http://example.com/2021/04/19/24-反转链表/

Author

John Doe

Posted on

2021-04-19

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.