远方有你,伴余生

远方有你,伴余生

为什么面试常考链表反转

链表是常用的数据结构,同时也是面试常考点,链表为什么常考,因为链表手写时,大多都会有许多坑,比如在添加节点时因为顺序不对的话会让引用指向自己,因此会导致内存泄漏等问题,Java会有JVM管理内存,可能不会引起太大问题,如果是c、c++、c#,这些语言都需要手动释放内存,如果操作不当后果不堪设想。其原因就是程序员对(引用)指针的理解出现偏差。

如果不了解Java引用可以查看这篇博客:

怎样实现链表反转

翻转链表实现如下:

  public class Link {
    Node head;

    public void reverse() {
        if (head.isEmpty() || head.next.isEmpty()) return;
        Node cur = head.next;
        Node pre = head;

        while (cur!=null) {
            Node tmp = cur.next;

            cur.next = pre;  //变成了 cur-》pre-》源cur.next节点
            head.next = tmp;
                         //2->1->3 c:3 p:2  3->2->4(1节点直接被4覆盖),需要修改
            pre = cur;
            cur = tmp;
            tmp = null; //垃圾回收
        }
        head = pre;
     }

     public boolean isEmpty() {
        return head == null;
     }

  }

  class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
        next = null;
    }

    public boolean isEmpty() {
        return this == null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
 }

分析思路:
  一般尝试,如果直接while让cur.next=cur;在cur.next=cur之前拿到cur.next的下一个节点,会出现子级指向自己的死环,这是不可取的。
  换一个方法,如果多添加一个是否会有帮助,添加一个pre=head引用,让cur移动一个单位,现在cur从head.next的位置,让cur的下一个位置
保存pre引用的地址,在cur的下一位置重新指向前事先让pre指向cur.next节点
源码如下:

    while ()
   {
            pre.next = cur.next;
            cur.next = pre;  //变成了 cur-》pre-》源cur.next节点

            Node tmp = pre;    //2->1->3 c:3 p:2  3->2->4(1节点直接被4覆盖),需要修改
            pre = cur;
            cur = tmp;
            tmp = null; //垃圾回收
    }

很明显,源码中并没有未排序的部分添加到链表尾部,而是直接放到了pre节点的后边,造成了污染数据的后果,经过修改后就是上面带实现类源码。

  如果不明白为什么是head.next=tmp;假如有一个链表是1->2->3->4,第一次翻转时候都是让cur放到pre的前面,再把没有排序的部分放到后边,如果第二次在按照这个思路跑的话,就会变成3->2->4,就会把原来2后边的1覆盖了,这里就有问题了,后边的节点不应该放到2后边,而是应该放到1,这个1正好是原来链表的head节点,所以每次添加的位置应该是head后边。

最后结果

最后跑完的结果是:

DEBUG:
  Node{val=4, next=Node{val=3, next=Node{val=2, next=Node{val=1, next=null}}}}

07-28 03:37