首页 > 面试热题TOP1-反转链表
头像
蘑菇睡不着
编辑于 2021-05-25 10:49
+ 关注

面试热题TOP1-反转链表

髣髴兮若轻云之蔽月,飘飖兮若流风之回雪。

一、题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

二、思路分析:

  这道题的意思是反转整个链表,其实链表中元素的位置并不用动,只要将所有节点指向下一个节点的指针,指向自己的前方的节点就可以了,大家可以直接看代码,思路通过注释进行了详细的解释。

三、AC代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode node = head;
        // 用于当作每个节点的前一个节点
        ListNode prev = null;

        while (node != null) {
            // 先存储每个节点的下一个节点 
            ListNode next = node.next;
            // 将指针指向前一个节点
            node.next = prev;
            // 将当前节点作为下一个节点的前置节点
            prev = node;
            // 往后移
            node = next;
        }
        return prev;
    }
}

时间复杂度:O(n),其中 n 是链表的长度,要遍历一次链表
空间复杂度:O(1)。

四、总结

  这道题就是将每个节点指向下一个节点指针指向前一个节点,写的时候有一点要注意,就是每次要先存储下一个节点再去做逻辑。

如果觉得文章还不错就点个赞+关注呗~

更多模拟面试

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐