微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

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

2019-02-20 16:56 算法与数据结构

来自:程序员小灰(微信号:chengxuyuanxiaohui)



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








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




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














让我们从链表头部开始,建立三个临时节点的引用,分别为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所在的节点成为逆序链表的头节点。




 
           
  1. private static Node head;



  2. public static void reverseLinkedList(){

  3.    if(head==null || head.next==null){

  4.        return;

  5.    }


  6.    Node p1 = head;

  7.    Node p2 = head.next;

  8.    Node p3 = null;


  9.    while (p2!=null){

  10.        p3 = p2.next;

  11.        p2.next = p1;

  12.        p1 = p2;

  13.        p2 = p3;

  14.    }


  15.    head.next = null;

  16.    head = p1;

  17. }



  18. private static class Node {

  19.    int data;

  20.    Node next;


  21.    Node(int data) {

  22.        this.data = data;

  23.    }

  24. }



  25. public static void main(String[] args){

  26.    //初始化链表

  27.    head = new Node(3);

  28.    head.next = new Node(5);

  29.    Node temp = head.next;

  30.    temp.next = new Node(1);

  31.    temp = temp.next;

  32.    temp.next = new Node(4);

  33.    temp = temp.next;

  34.    temp.next = new Node(9);


  35.    //逆序前输出链表

  36.    temp = head;

  37.    while(temp!=null){

  38.        System.out.println(temp.data);

  39.        temp = temp.next;

  40.    }


  41.    //逆序链表

  42.    reverseLinkedList();


  43.    //逆序后输出链表

  44.    temp = head;

  45.    while(temp!=null){

  46.        System.out.println(temp.data);

  47.        temp = temp.next;

  48.    }

  49. }


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






●编号853,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐25个技术类公众微信

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

 
算法与数据结构 更多文章 网易组建Python数据分析学习群,2场免费直播课带你入门Python数据分析 2019年2月编程语言排行榜:Python稳坐前三,Visual Basic.NET迅猛增长 史上最污技术解读,我竟然秒懂了! 年后跳槽必看,这份书单让你分分钟拿下offer 上班啦,年后BATJ开聘都是这种人....
猜您喜欢 perl爬虫01-花瓣网相册 WebVirtMgr管理平台介绍 [HBR案例分享]都市丽人: 零售的本质就是数据 企业级Docker镜像中心(一)Harbor的安装和配置指导 史无前例开放!阿里内部集群管理系统Sigma混布数据