算法通关第一村-链表黄金挑战(Java)

03-01 1239阅读

算法通关第一村-链表黄金挑战(Java)

本关我们只研究两道题，一个是链表中环的问题，一个是双向链表问题。

链表中环的问题，具体来说是两道题。如何确定链表中环的问题，这个问题如果用Hash或者集合非常简单，但是在面试的时候如果这么做就没什么思维含量了，所以我们需要另外想办法。如何寻找入口问题。

双向链表在工程里有很多应用，在操作系统、JVM等基础框架也有大量应用，因此也非常值得我们学习。

1.链表中环的问题

本题同样是链表的经典问题。给定一个链表，判断链表中是否有环，这就是LeetCode141。进一步，假如有环，那环的位置在哪里？这就是LeetCode 142题。
这个问题前一问相对容易一些，后面一问比较难想到。但是，假如面试遇到第一问了，面试官很可能会问第二个，因为谁都知道有这个一个进阶问题。就像你和女孩子表白成功后，你会忍不住进阶一下——“亲一个呗”，一样的道理，所以我们都要会。

示例1：
输入：head = [3, 2, 0, -4]，pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

判断是否有环，最容易的方法是使用 Hash，遍历的时候将元素放入到 map 中，如果有环一定会发生碰撞。发生碰撞的位置也就是入口的位置。

   public LinkListNode detectCycle(LinkListNode head){
          LinkListNode pos = head;
          Set visited = new HashSet();
          while(pos != null){
              if(visited.contains(pos)){
                  return pos;
              }else{
                  visited.add(pos);
              }
              pos = pos.next;
          }
          return null;
      }

1.1为什么快慢两个指针一定会相遇

确定是否有环，最有效的方法就是双指针，一个快指针（一次走两步），一个慢指针（一次走一步）。如果快的能到达表尾就不会有环，否则如果存在环，则慢指针一定会在某个位置与快指针相遇。这就像在操场长跑，一个人快一个人慢，只要时间够，快的一定能在某个时候再次追上慢的人（也就是所谓的套圈）。
这里很多人可能会有疑问，因为两者每次走的距离不一样，会不会快的人在追上慢的时候跳过去了导致两者不会相遇呢？不会！如下图所示，当fast快要追上slow的时候，fast一定距离slow还有一个空格，或者两个空格，不会有其他情况。
假如有一个空格，如上图情况1所示，fast和slow下一步都到了3号位置，因此就相遇了。
假如有两个空格，如上图情况2所示，fast下一步到达3，而slow下二步到达4，这就变成了情况1了，因此只要有环，一定会相遇。
使用双指针思想寻找是否存在环的方法：

  public boolean hasCycle(LinkListNode head){
          if(head == null || head.next == null){
              return false;
          }
          LinkListNode fast = head, slow = head;
          while(fast != null && fast.next != null){
              fast = fast.next.next;
              slow = slow.next;
              if(fast == slow){
                  return true;
              }
          }
          return false;
      }

1.2确定入口的方法

这里的问题是如果知道了一定有入口，那么如何确定入口的位置呢？方法非常简单，但是要理解清楚有些难度。

先说结论先按照快慢方式寻找到相遇的位置（假如为下图中Z），然后将两指针分别放在链表头（X）和相遇位置（Z），并改为相同速度推进，则两指针在环开始位置相遇（Y）。
结论很简单，但这是为什么呢？

①先看假如一圈就遇到的情况

为了便于理解，我们首先假定快指针在第二次进入环的时候就相遇了：

此时的过程是：

找环中相汇点。分别用fast、slow表示快慢指针，slow每次走一步，fast就走两步，直到在环中的某个位置相会，假如是图中的Z。
第一次相遇：
那么我们可以知道fast指针走了a+b+c+b步，slow指针走了a+b步
那么：
2*(a+b) = a+b+c+b
所以a=c
因此此时让slow从Z继续向前走，fast回到起点，两个同时开始走（两个每次都走一步），一次走一步那么它们最终会相遇在y点，正是环的起始点。

② 如果多圈之后才相遇
如果是走了多圈之后才遇到会怎么样呢？设链表中环外部分的长度为 a。slow 指针进入环后，又走了b的距离与 fast相遇。此时，fast 指针已经走完了环的n圈，因此它走过的总距离为：
Fast: a+n(b+c)+b=a+(n+1)b+nc
根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的2倍。因此，我们有：
a+(n+1)b+nc=2(a+b)
由于b+c就是环的长度，假如为LEN，则：
a=c+(n-1)LEN
这说明什么呢？说明相遇的时候快指针在环了已经转了（n-1）LEN圈，如果n-1就退化成了我们上面说的一圈的场景。假如n是2，3，4，⋯呢，这只是说明当一个指针p1重新开始从head走的时候，另一个指针p2从Z点开始，两者恰好在入口处相遇，只不过p2要先在环中转n-1圈。
当然上面的p1和p2要以相同速度，我们发现slow和fast指针在找到位置Z之后就没有作用了，因此完全可以用slow和fast来代表p1和p2。因此代码如下：

  public LinkListNode detectCycle2(LinkListNode head){
          if(head == null){
              return null;
          }
          LinkListNode fast = head, slow = head;
          while(fast != null){
              slow = slow.next;
              if(fast.next != null){
                  fast = fast.next.next;
              }else{
                  return null;
              }
              if(fast == slow){//找到相遇的位置
                  fast = head;//fast返回
                  while(fast != slow){
                      fast = fast.next;
                      slow = slow.next;
                  }
                  return fast;//环的入口
              }
          }
          return null;
      }

2.双向链表

2.1基本概念

双向链表顾名思义就是既可以向前，也可以向后。有两个指针的好处就是移动元素方便。该结构在工程里有大量应用。

  public class DoubleLinkedNode {
      public int data;
      public DoubleLinkedNode next;
      public DoubleLinkedNode prev;
      public DoubleLinkedNode(int data){
          this.data = data;
      }
  }

2.2插入元素

2.2.1头插法

  public class InsertElement {
      DoubleLinkedNode first = null;
      DoubleLinkedNode last = null;
      public static void main(String[] args) {
  
      }
  
      //头插法
      public void insertHead(int data){
          DoubleLinkedNode newDoubleNode = new DoubleLinkedNode(data);
          if(first == null){
              last = newDoubleNode;
          }else{//此时插入的不是第一个节点的情况
              first.prev = newDoubleNode;
          }
          newDoubleNode.next = first;
          //将新节点赋给 first 成为第一个节点
          first = newDoubleNode;
      }

以 insertHead(int data) 为例，从双向链表为空到插入 20,40,60。首先 first 和 last 都指向 null。

先看执行如下代码的时候结构：
然后执行 first = newDoubleNode；之后的结构：
这样就插入了第一个元素。

这样链表就是 first 指向节点 60，然后指向节点 20,40。

2.2.2尾插法

  public class InsertElement {
      DoubleLinkedNode first = null;
      DoubleLinkedNode last = null;
      public static void main(String[] args) {
  
      }
  
      //尾插法
      public void insertTail(int data){
          DoubleLinkedNode newDoubleNode = new DoubleLinkedNode(data);
          if(first == null){
              first = newDoubleNode;
          }else{//此时插入的不是第一个节点的情况
              last.next = newDoubleNode;
              newDoubleNode.prev = last;
          }
          //将新节点赋给 first 成为第一个节点
          last = newDoubleNode;
      }
  }

2.2.3链表中间插入

  public class InsertElement {
      DoubleLinkedNode first = null;
      DoubleLinkedNode last = null;
      public static void main(String[] args) {
  
      }
  
      //中间插入
      public void insertAfter(int key, int data){
          DoubleLinkedNode newDoubleNode = new DoubleLinkedNode(data);
          DoubleLinkedNode current = first;
          if((current != null) && (current.data != key)){
              current = current.next;
          }
          //如果当前节点 current 为空
          if(current == null){
              //1.如果本身为空链表
              if(first == null){
                  first = newDoubleNode;
                  last = newDoubleNode;
              }else{//2.如果链表非空且其中中没有值为key的节点
                  last.next = newDoubleNode;
                  newDoubleNode.prev = last;
                  last = newDoubleNode;
              }
          }else{//找到值为key的节点
              if(current == last){
                  //3.key 值 与最后的节点的值相等
                  newDoubleNode.next = null;
                  last = newDoubleNode;
              }else{
                  /4./链表中有值为 key,在两节点中间插入
                  newDoubleNode.next = current.next;
                  current.next.prev = newDoubleNode;
              }
              current.next = newDoubleNode;
              newDoubleNode.prev = current;
          }
      }
  }

2.3删除元素

2.3.1删除首元素

  public DoubleLinkedNode deleteHead(){
          DoubleLinkedNode temp = first;
          //若链表只有一个节点，删除后链表为空，将last = null
          if(first.next == null){
              last = null;
          }else{
              //若链表的节点不止一个，则将 first.next 变成第一个节点
              first.next.prev = null;
          }
          first = first.next;
          //返回被删除的节点
          return temp;
      }

2.3.2删除尾节点

  public DoubleLinkedNode deleteTail(){
          DoubleLinkedNode temp = last;
          //若链表只有一个节点，删除后链表为空，将last = null
          if(first.next == null){
              first = null;
          }else{
              //若链表的节点不止一个，则将上一个节点的 next域 指向null
              last.prev.next = null;
          }
          //上一个节点成为最后一个节点，last 指向它
          last = last.prev;
          //返回被删除的节点
          return temp;
      }

2.3.3删除中间元素

我们只需调整两个指针，一个是 cur.next 的 prev指向 cur.prev，第二个是 cur.prev 的 next 指向 cur.next。此时 cur节点没有节点访问了，根据垃圾回收算法，此时 cur就变得不可达，最终被回收掉，所以这样就完成了删除 cur的操作。

  public DoubleLinkedNode detectKey(int key){
          DoubleLinkedNode current = first;
          //遍历链表寻找 key值 的节点
          if((current != null) && (current.data != key)){
              current = current.next;
          }
          //如果链表为空链表或者没有值为 key 的节点则返回 null
          if(current == null){
              return null;
          }else{
              //如果 current是第一个节点
              if(current == first){
                  first = current.next;
                  current.next.prev = null;
              }else if(current == last){
                  //如果 current是最后一个节点
                  last = current.prev;
                  current.prev.next = null;
              }else{
                  current.next.prev = current.prev;
                  current.prev.next = current.next;
              }
          }
          //返回被删除的节点
          return current;
      }

rrent == last){

//如果 current是最后一个节点

last = current.prev;

current.prev.next = null;

}else{

current.next.prev = current.prev;

current.prev.next = current.next;

}

//返回被删除的节点

return current;

}

```

VPS购买请点击我

算法通关第一村-链表黄金挑战(Java)

算法通关第一村-链表黄金挑战(Java)

1.链表中环的问题

1.1为什么快慢两个指针一定会相遇

1.2确定入口的方法

2.双向链表

2.1基本概念

2.2插入元素

2.2.1头插法

2.2.2尾插法

2.2.3链表中间插入

2.3删除元素

2.3.1删除首元素

2.3.2删除尾节点

2.3.3删除中间元素

相关阅读

怎么把织梦的模板替换?

dedecms怎么调用特定的栏目文档?

怎么抓包一个网页?

wap怎么封装app?

目录[+]