LeetCode 206. 反转链表

题目描述

🔥 206. 反转链表

image-20230716223615915

image-20230716223621258

思路分析

  1. 头插法
  2. 递归

image-20201019211501298

参考代码

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)，只使用了常数级别的额外空间。

🍏 点击查看 Java 题解(一)

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;
    }
}

🍏 点击查看 Java 题解(二)

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;
    }
}
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/71018228
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！