Welcome everyone

每周一练(1)

每周一练 汪明鑫 268浏览 0评论

算法和SQL和Java API菜鸟【练习专题】,大佬绕过哈

 

反转一个单链表。

示例:

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

 

上代码:
链表node

public class ListNode {

    int var;
    ListNode next;

    public ListNode(int var) {
        this.var = var;
    }
}

 

public class ReverseLinedList {

    public ListNode reverse(ListNode origin){
        if(origin == null){
            return origin;
        }

        ListNode pre = null;
        ListNode cur = origin;
        ListNode next = null;

        //反转核心代码
        while (cur.next!=null){
            //next 指针记录后面的元素,否则会断掉
            next = cur.next;
            cur.next = pre;

            //pre、cur一起右移
            pre = cur;
            cur = next;
        }

        //到链表末尾的特殊处理 cur.next == null; 最后一处还未反转
        cur.next = pre;

        return cur;

    }

}

 

复杂度分析:

  • 时间复杂度:假设  是列表的长度,时间复杂度是 
  • 空间复杂度:O(1)

 

 

如果把cur的next指向pre,那么就会和后面的结点断掉

因此我们需要一个next指针指向cur的下一个结点

 

 

中间状态:

 

cur==null 跳处循环后:

 

终态:

链表反转成功!

 

每周坚持一练

不把保持坚持认为是一个需要坚持的事情

 

 

转载请注明:汪明鑫的个人博客 » 每周一练(1)

喜欢 (0)

说点什么

您将是第一位评论人!

提醒
avatar
wpDiscuz