前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >漫画:如何将一个链表“逆序”?

漫画:如何将一个链表“逆序”?

作者头像
AndroidTraveler
发布2019-02-25 11:20:35
6180
发布2019-02-25 11:20:35
举报
文章被收录于专栏:AndroidTraveler

————— 第二天 —————

(现实里的小灰在刚入行的时候,面试官也问了我这个问题,当时小灰就傻傻的问面试官是单链表还是双链表?然后就没然后了......)

————————————

让我们从链表头部开始,建立三个临时节点的引用,分别为p1,p2,p3。它们分别指向头节点、第二个节点、第三个节点。

实现链表逆序的完整步骤如下:

1.以p2节点为视角,把p2节点原本指向p3的next指针倒转,指向p1。

2.三个临时节点引用p1,p2,p3分别向后移动一格位置。

3.重复第1步的工作,以p2节点为视角,把p2节点原本指向p3的next指针倒转,指向p1。

4.重复第2步的工作,三个临时节点引用p1,p2,p3分别向后移动一格位置。

.......

.......

5.继续像这样子迭代下去,一直到p2是空为止。

6.最后,把head节点的next指向空,成为逆序链表的尾节点。并且把p1赋值给head,让p1所在的节点成为逆序链表的头节点。

代码语言:javascript
复制
private static Node head;


public static void reverseLinkedList(){
    if(head==null || head.next==null){
        return;
    }

    Node p1 = head;
    Node p2 = head.next;
    Node p3 = null;

    while (p2!=null){
        p3 = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = p3;
    }

    head.next = null;
    head = p1;
}


private static class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}


public static void main(String[] args){
    //初始化链表
    head = new Node(3);
    head.next = new Node(5);
    Node temp = head.next;
    temp.next = new Node(1);
    temp = temp.next;
    temp.next = new Node(4);
    temp = temp.next;
    temp.next = new Node(9);

    //逆序前输出链表
    temp = head;
    while(temp!=null){
        System.out.println(temp.data);
        temp = temp.next;
    }

    //逆序链表
    reverseLinkedList();

    //逆序后输出链表
    temp = head;
    while(temp!=null){
        System.out.println(temp.data);
        temp = temp.next;
    }
}

链表反转的逻辑本身,都在reverseLinkedList方法当中。在这里我们把链表的头节点作为了静态成员,实际上也可以作为方法参数传入,只是逻辑上需要一些小小的修改。

如果喜欢本文,请给个好看,觉得特别喜欢,请转发给你的朋友们。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 安卓小煜 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档