LeetCode 206. 反转链表
题目描述
思路分析
- 头插法
- 递归
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
cur := head
var pre *ListNode
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
1
2
3
4
5
6
7
8
9
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
- 时间复杂度：
O(n)，其中n是链表的节点数。我们需要遍历每个节点一次。- 空间复杂度：
O(1)，只使用了常数级别的额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！