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

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






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

程序员小灰

推荐↓↓↓
算法与数据结构
上一篇:LeetCode 算法 | 如何拆分数组? 下一篇:必学十大经典排序算法,看这篇就够了(附完整代码/动图/优质文章)