单向链表逆转

冷不防 2023-07-13 03:20 29阅读 0赞

不善言谈的优秀程序员在面试中往往是要吃巨亏的，你没有办法通过说话来轻易证明自己的实力。不论是大厂还是小厂，大部分面试官都不具备优秀的面试能力，它们也只能通过三言两语观察一下面试者的表面工夫。老钱就是这样吃了很多亏的程序员，不喜欢准备面试，不喜欢吹嘘虚假的不存在的经验和能力，甚至连网上的笔试题都懒得做，因为在实际工作中这些鸟题根本一点都用不上。

但是这并不是什么值得骄傲的真诚，面试不做准备是对目标企业的不尊重，也是个人性格上自大的一种表现。虽然所有的面试官都希望面试者是真实的无虚假的不做表面文章的，但是这样的人真的站在你面前时，几乎所有的面试官往往又都看不上。

那如何在尽量少做表面功夫的基础上让面试官能够看上你？其中的方法之一就是展现平时个人优秀的作品和实现代码，但是这需要时间需要实打实的功夫，能够有机会作出优秀个人作品的人并不多见，大多数人都在忙碌的工作中耗尽了所有的时间。那还有一个方法就是在笔试阶段大显身手，让自己优秀的代码能力跃然纸上，让面试官瞬间对你产生不一样的感觉。

不要被笔试阶段那些算法题给吼到了，在你眼里似乎它们是为程序天才们准备的。其实大多数公司的笔试题也是来源于网上，那些被无数人做烂的题目。你被题目搞晕了而别人没有，那是因为别人已经做过这道题了，而不是智商所致。

就拿今天我要讲的算法题 —— 逆转单向链表，它是一个非常简单的题目，但是如果你是第一次见到这道题，将它完完整整没有 bug 的写出来是着实需要费一番功夫的。期望在那短短的笔试题环节就轻松搞定这道题，那真是非常有算法天赋的人才能做到的事。难道大厂里面的程序员个个都是天才，鬼才相信。天才总是极少数的，多数都是像老钱这样的庸才。

好，言归正传，下面我们开始讲解今天的算法题 —— 逆转单向链表。首先这是一个单向的链表，不同于 Java 里面的 LinkedList，它是双向的链表。链表中每个节点之间通过 next 指针串接起来，会有一个链表头和链表尾指针 hold 住整个链表。逆转的任务就是将 head -> a -> b -> c -> d <- tail 变成 head -> d -> c -> b -> a <- tail。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70][]  
链表结构表示

![2020030921180544.png][]

class Node<T> {
        T value;
        Node<T> next;
     
        Node(T value) {
            this.value = value;
        }
    }
     
    class ReverseLinkedList<T> {
      Node<T> head, tail;
    }

链表构造器  
我们需要将所有的元素一个一个的使用 next 指针串接起来，链表的头尾节点要用 head 和 tail 变量把持住。加入新元素时，需要调整尾部节点的 next 指针，指向新加入的元素节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 1][]

class ReverseLinkedList<T> {
      private Node<T> head, tail;
     
      public ReverseLinkedList(T... values) {
        for (T value : values) {
            if (tail == null) {
                // 第一个节点
                head = tail = new Node<>(value);
            } else {
                // 后面的节点往链表尾部追加
                Node<T> oldTail = tail;
                oldTail.next = tail = new Node<>(value);
            }
        }
      }
    }
    
    
    ReverseLinkedList<Integer> l = new ReverseLinkedList<>(1,2,3,4,5,6);

链表内容呈现

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 2][]  
我们需要提供一个链表的输出方法，以便快速对比逆转后链表的内容是否正确

class ReverseLinkedList<T> {
      private Node<T> head, tail;
     
      public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        Node<T> cur = head;
        while (cur != null) {
            sb.append(cur.value);
            cur = cur.next;
            if (cur != null) {
                sb.append(',');
            }
        }
        sb.append(']');
        return sb.toString();
      }
    }

迭代逆转算法  
循环调整 next 指针是最容易想到的方法，但是要将指针精确地逆转正确其实并不容易。下面代码中的循环部分很短，但是却很精致，使用了三个临时局部变量 cur、next 和 nextnext，稍有不慎就会出错。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 3][]  
当我写完下面这段代码时，虽然可以正常运行出期望的结果，但是总当心哪里会有遗漏，是不是什么地方少了个 if else，这就是编写算法代码时常见的心理状态。

class ReverseLinkedList<T> {
      private Node<T> head, tail
     
      public ReverseLinkedList<T> reverseByLoop() {
        // 空链表或者单元素都无需处理
        if (head == tail) {
            return this;
        }
        Node<T> cur = head;
        Node<T> next = cur.next;
        while (next != null) {
            Node<T> nextnext = next.next;
            next.next = cur;
            cur = next;
            next = nextnext;
        }
        tail = head;
        tail.next = null;
        head = cur;
        return this;
      }
    }

递归逆转算法  
使用递归的思想来解决这个问题也是一个很好的主意，只不过当链表特别长时，调用栈会很深，链表长到一定程度就会抛出臭名昭著的异常 StackOverflowException。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 4][]

class ReverseLinkedList<T> {
      private Node<T> head, tail
     
      public ReverseLinkedList<T> reverseByRecursive() {
        Node<T> oldTail = tail;
        tail = reverseFrom(head);
        tail.next = null;
        head = oldTail;
        return this;
      }
     
      private Node<T> reverseFrom(Node<T> from) {
          if (from == tail) {
          return from;
        }
        Node<T> end = reverseFrom(from.next);
        end.next = from;
        return from;
      }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309211708809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI=,size_16,color_FFFFFF,t_70
[2020030921180544.png]: https://img-blog.csdnimg.cn/2020030921180544.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200309211840524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200309212154369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200309212458103.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200309212643291.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTEwNTE5MTI=,size_16,color_FFFFFF,t_70