算法和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;

    }

}

复杂度分析：

• 时间复杂度：假设 $n$ 是列表的长度，时间复杂度是 $O(n)$
• 空间复杂度：O(1)

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

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

中间状态：

cur==null 跳处循环后：

终态：

链表反转成功！

每周坚持一练

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

转载请注明：汪明鑫的个人博客 » 每周一练（1）