专栏首页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所在的节点成为逆序链表的头节点。

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方法当中。在这里我们把链表的头节点作为了静态成员,实际上也可以作为方法参数传入,只是逻辑上需要一些小小的修改。

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

本文分享自微信公众号 - 安卓小煜(AndroidTraveler)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Android 8.0 的部分坑及对应解决方法

    但是迟到好过不到,因此基于此这边还是记录一下项目中遇到的 Android 8.0 的坑及对应解决方法。

    AndroidTraveler
  • Android Q 兼容那些事

    5 月 20 号参加了 Android Q Labs,因此本篇说一说会议的部分内容以及自己的一些想法。

    AndroidTraveler
  • Flutter 即学即用系列博客——09 MethodChannel 实现原生与 Flutter 通信(二)

    上一篇我们讲解了如何通过 EventChannel 实现 Android -> Flutter 的通信。

    AndroidTraveler
  • 链表倒数第n个节点

    一份执着✘
  • 【CPP】《程序员面试金典》习题(2)——链表

    这次的题比较少,题目的主题是链表,最值得注意的是快慢指针的用法和最后一题的Floyd判圈算法。

    ZifengHuang
  • 3Python标准库系列之os模块

    py3study
  • 刷题之合并K个排序链表

    从21. 合并两个有序链表的基础上,我们已经能够解决两个有序链表的问题,现在是k个有序链表,我们可以将第一二个有序链表进行合并,然后将新的有序链表再继续跟第三个...

    小歪
  • 华为面试题——单向链表倒转(一次遍历)

    /*     Blog: http://blog.csdn.net/jiangxinnju     function:     将单向链表reverse...

    用户1221057
  • 工厂方法模式

    上文描述了简单工厂模式,但是简单工厂模式并不属于23种设计模式。所以本文我们介绍简单工厂模式的高级实现。在此之前先看一下简单工厂模式所存在的问题。预留问题:

    乱敲代码
  • Android SDK以及

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明...

    bering

扫码关注云+社区

领取腾讯云代金券