题解 | #反转链表#

反转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

假设单链表为如下: alt 解题思路:使用头插法,遍历链表的同时进行头插。

​ 我们先定义两个指针 cur 和 curNext,cur表示当前遍历位置的节点,curNext表示cur的下一个节点,cur从head开始。

首先将head置为null,代表链表末尾节点的next。 alt 然后从cur开始进行头插,让cur.next = head; head = cur,注意一定要将curNext赋值,不然就会丢失后面的节点。

实现代码:

public ListNode reverseList(ListNode head) {
    if (null == head) return null; // 判断空链表

    ListNode cur = head; // 从head开始
    head = null; // 将head置为null
    while (null != cur) { // 遍历整个链表
        ListNode curNext = cur.next; // 先保存cur后面的子链表
        cur.next = head; // 头插
        head = cur;
        cur = curNext;
    }

    return head;
}

​ 时间复杂度O(N):N为单链表的长度,需要遍历每个节点一次。

​ 空间复杂度O(1):使用几个常量大小的临时变量。

#面试题打卡学习#
全部评论

相关推荐

04-11 23:51
门头沟学院 Java
坚定的芭乐反对画饼_许愿Offer版:人人都能过要面试干嘛,发个美团问卷填一下,明天来上班不就好了
点赞 评论 收藏
分享
05-12 17:28
已编辑
门头沟学院 硬件开发
ldf李鑫:不说公司名祝你以后天天遇到这样的公司
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务