乐趣区

关于java:有关链表的小技巧我都给你总结好了

jiezi

链表

链表是数据结构里一个很根底然而又很爱考的线性构造，链表的操作相对来说比较简单，然而非常适合考查面试者写代码的能力，以及对 corner case 的解决，还有指针的利用很容易引起 NPE (null pointer exception)。综合以上起因，链表在面试中很重要。

提到链表就不得不提数组，它和数组能够说是数据结构的根底，那么它们最次要的区别在于：

  • 数组在物理内存上必须是间断的
  • 链表在物理内存上不须要间断，通过指针连贯

所以数组最好的性质就是能够随机拜访 random access，有了 index，能够 O(1) 的工夫拜访到元素。

而链表因为不间断，所以无奈 O(1) 的工夫定位任意一个元素的地位，那么就只能从头开始遍历。

这就造成了它们之间增删改查上效率的不同。

除此之外，链表自身的构造与数组也是齐全不同的。

LinkedList 是由 ListNode 来实现的：

class ListNode {
  int value;
  ListNode next;
}

构造上长这样：

这是单向链表，那还有的链表是双向链表，也就是还有一个 previous pointer 指向以后 node 的前一个 node：

class ListNode {
  int value;
  ListNode next;
  ListNode prev;
}

其实链表相干的题目没有很难的，套路也就这么几个，其中最常考最根底的题目是反转链表，据说微软能够用这道题电面刷掉一半的 candidate，两种办法一遍 bug free 还是不容易的。文章之前曾经写过了，点击这里中转温习。

明天咱们来说链表中 最次要的 2 个技巧 ： 双指针法 和 dummy node，置信看完本文后，链表相干的绝大多数题目你都能搞定啦。

双指针法

双指针法在很多数据结构和题型中都有利用，在链表中用的最多的还是 快慢指针。

顾名思义，两个指针一个走得快，一个走得慢，这样的益处就是以不同的速度遍历链表，不便找到指标地位。

常见的问题比方找一个链表的中点，或者判断一个链表是否有环。

例 1：找中点

这题就是给一个链表，而后找到它的中点，如果是奇数个很好办，如果是偶数个，题目要求返回第二个。

比方：

1 -> 2 -> 3 -> 4 -> 5 -> NULL，须要返回 3 这个 ListNode；

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL，须要返回 4 这个 ListNode。

但其实吐槽一下，如果真的要设计一个这样的 API，我更偏向于抉择返回偶数个中的第一个中点。

为什么呢？

算法题都是工业生产中一些问题的形象。比如说咱们找中点的目标是为了把这个链表断开，那么返回了 3，我能够断开 3 和 4；然而返回了 4，单向链表我怎么断开 4 之前的中央呢？还得再来一遍，麻烦。

Solution

办法一、

这题最直观的解法就是能够先求这个链表的长度，而后再走这个长度的一半，失去中点。

class Solution {public ListNode middleNode(ListNode head) {if(head == null) {return null;}

        int len = 0;
        ListNode current = head;
        while(current != null) {
            len++;
            current = current.next;
        }

        len /= 2;
        ListNode result = head;
        while(len > 0) {
            result = result.next;
            len--;
        }

        return result;
    }
}

办法二、快慢指针

咱们用两个指针一起来遍历这个链表，每次快指针走 2 步，慢指针走 1 步，这样当快指针走到头的时候，慢指针应该刚好在链表的中点。

class Solution {public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

这两个办法孰优孰劣呢？

网上很多说什么办法一过了两遍链表，办法二只过了一遍。

但其实，然而办法二用了两个指针来遍历，所以两个办法过的遍数都是一样的。

它们最大的区别是：

办法一是 offline algorithm，办法二是 online algorithm。

公司里的数据量是源源不断的，比方电商零碎里总有客户在下单，社交软件里的好友增长是始终在涨的，这些是数据流 data stream，咱们是无奈计算数据流的长度的。

那么 online algorithm 可能给时刻给出以后的后果，不用说等数据全副录入实现后，实际上也录不完。。这是 online algorithm 比 offline algorithm 大大的劣势所在。

更多的解释大家能够参考 stack overflow 的这个问题，链接在文末。

例 2：判断单链表是否有环

思路：快慢指针一起从 head 登程，每次快指针走 2 步，慢指针只走 1 步，如果存在环，那么两个指针肯定会相遇。

这题是典型的龟兔赛跑，或者说在操场跑圈时，跑的快的同学总会 套圈 跑的慢的。

public class Solution {public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {return true;}
        }
        return false;
    }
}

这题有个升级版，就是要求返回环的终点。

例 3：返回有环链表的环的终点

这题我感觉不全是个算法题了，还是个数学题哈哈。

先摆出论断：

  1. 快慢指针从链表头开始走，相遇的那点，记为 M；
  2. 再用 2 个指针，一个从头开始走，一个从 M 开始走，相遇点即为 cycle 的终点。

咱们先看形象进去的图：

假如快慢指针在 M 点第一次相遇，

这里咱们设 3 个变量来示意这个链表里的几个重要长度：

  • X：从链表头到环的终点的长度；
  • Y：从环的终点到 M 点的长度；
  • Z：从 M 点到环的终点的长度。

留神：因为环是有方向的，所以 Y 并不是 Z。

那其实咱们惟一晓得的关系就是：快慢指针在 M 点第一次相遇。这也是咱们最后假如的关系。

而快慢指针有一个永远不变的真谛：快指针走的长度永远是慢指针走的长度的 2 倍。

相遇时快慢指针别离走了多少的长度呢？

  • 快指针：X+ Y + 假如走了 k 圈
  • 慢指针：X + Y

那么咱们就能够用这个 2 倍的关系，列出下列等式：

2 * (X + Y) = X + Y + kL

所以 X + Y = kL

而咱们留神到：Y + Z = L，那么就能得出 X = Z。

所以当两个指针，一个从头开始走，一个从 M 点开始走时，相遇那点就是环的终点，证毕。

来看下代码吧：

public class Solution {public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
​      if (slow == fast) {
​        ListNode x = head;
​        ListNode y = slow;
​        while(x != y) {
​          x = x.next;
​          y = y.next;
​        }
​        return x;
​      }
​    }
​    return null;
  }
}

这题还有个利用，就是找一个特定数组里反复的数字，这里就不开展了，大家感兴趣的去做一下吧～

接下来咱们聊聊 dummy node 这个技巧。

Dummy node

Dummy 的中文是“假”的意思，dummy node 大略能够翻译成虚构节点？有更纯粹的说法的话还请大家在评论区通知我呀～

一般来说，dummy node 的用法是在链表的实在 head 的后面加一个指向这个 head 的节点，目标是为了不便操作 head。

对于链表来说，head 是一个链表的灵魂，因为无论是查问还是其余的操作都须要从头开始，俗话说擒贼先擒王嘛，抓住了一个链表的头，就抓住了整个链表。

所以当须要对现有链表的头进行改变时，或者不确定头部节点是哪个，咱们能够事后加一个 dummyHead，这样就能够灵活处理链表中的残余局部，最初返回时去掉这个“假头”就好了。

很多时候 dummy node 不是必须，然而用了会很不便，缩小 corner case 的探讨，所以还是十分举荐应用的。

光说不练假把式，咱们间接来看题～

例 4：合并两个排好序的链表

这题有很多种解法，比方最直观的就是用两个指针，而后比拟大小，把小的接到最终的后果下来。

然而有点麻烦的是，最初的后果不晓得到底谁是头啊，是哪个链表的头作为了最终后果的头呢？

这种状况就非常适合用 dummy node。

先用一个虚构的头在这撑着，把整个链表结构好之后，再把这个假的剔除。

来看代码～

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {​    if (l1 == null) {
​      return l2;
​    }
​    if (l2 == null) {
​      return l1;
​    }
​    ListNode dummy = new ListNode(0);
​    ListNode ptr = dummy;
​    while (l1 != null && l2 != null) {​      if (l1.val < l2.val) {
​        ptr.next = l1;
​        l1 = l1.next;
​      } else {
​        ptr.next = l2;
​        l2 = l2.next;
​      }
​      ptr = ptr.next;
​    }
​    if (l1 == null) {
​      ptr.next = l2;
​    } else {
​      ptr.next = l1;
​    }
​    return dummy.next;
  }
}

这题也有升级版，就是合并 k 个排好序的链表。实质上也是一样的，只不过须要重写一下比拟器就好了。

例 5：删除节点

这道题的意思是删除链表中某个特定值的节点，可能有一个可能有多个，可能在头可能在尾。

如果要删除的节点在头的时候，新链表的头就不确定了，也有可能是个空的。。此时就很适宜用 dummy node 来做，躲避掉这些 corner case 的探讨。

那这题的思路就是：用 2 个指针

  • prev：指向以后新链表的尾巴
  • curr：指向以后正在遍历的 ListNode

如果 curr == 目标值，那就间接移到下一个；

如果 curr != 目标值，那就把 prev 指向它，接上。

这题须要留神的是，最初肯定要把 prev.next 指向 null，否则如果原链表的尾巴是目标值的话，还是去不掉。

代码如下：

class Solution {public ListNode removeElements(ListNode head, int val) {​    ListNode dummy = new ListNode(0);
​    ListNode prev = dummy;
​    ListNode curr = head;
​    while(curr != null) {​      if (curr.val != val) {
​        prev.next = curr;
​        prev = prev.next;
​      }
​      curr = curr.next;
​    }
​    prev.next = null;
​    return dummy.next;
  }
}

好了，以上就是本文的所有内容了，如果这篇文章对你有帮忙，欢送分享给你身边的敌人，也给齐姐点个「在看」，你们的反对是我创作的最大能源！

悄悄话

最近开明了视频号，精力扩散了许多，没想到录个 1 分钟的短视频也能这么多事。。

然而 公众号照常分享技术干货和《齐姐聊大厂》系列，还请大家持续关注反对呀，为了保障内容的优质在线，可能筹备工夫有点长，多谢大家的急躁期待～～如果想我了就来视频号里找我玩～

最初，如果你对小齐的文章或者视频有什么想法或倡议，欢送留言或者私信与我多多交换，我是小齐，终生学习者，咱们下期见！

退出移动版