Java写题解 | #反转链表#

反转链表

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

假设需要反转 X -> A- > B -> Y,仅考虑反转AB部分,那么只需要修改B.next 为A,但是这样的话B和Y之间的联系就断掉了。
为了避免上述的情况,比较好的办法就是提前存储一下Y的地址(或者指针)因此实际上需要三个指针来操作。
考虑到链表的实际情况,末尾上始终有一个空指针,即对于{ 1,2,3 }来说,实际情况为 1-> 2-> 3-> null, 因此可以设置从一个空指针开始。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode now = head;

        // while循环结束条件为now == null,即当前指针已经移动到链表尾的null处,只需要返回pre即可
        while (now != null) { 

            // 存储当前指针的next到post中
            ListNode post = now.next;

            // 将当前指针的next指向前一个指针
            now.next = pre;

            // 将指向前一个节点的指针移向当前指针指向的节点
            pre = now;

            // 将当前指针移动到下一个节点上
            now = post;
        }

        return pre;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 13:05
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:30
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务