面试精选之链表问题集锦

   <p>链表问题是面试过程中经常被问到的一部分，很考查编程功底。最近刷了 LeetCode 上链表部分的面试题，我总结了一些有代表性的链表问题。</p>    <p>本文使用的是 Java 语言，下面是所用到的链表节点的定义：</p>    <pre>  public class ListNode{      int val;      ListNode next;        ListNode(int x) {          val = x;      }  }  </pre>    <h2>1. 在 O(1) 时间删除链表节点</h2>    <p><a href="/misc/goto?guid=4959755644104369054" rel="nofollow,noindex">Leetcode 237. Delete Node in a Linked List</a></p>    <p>题目描述：给定单链表中需要删除的节点（不是尾节点），在 O(1) 时间删除该节点。</p>    <p>分析：本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。</p>    <p>代码如下：</p>    <pre>  // 在 O(1) 时间从无头单链表中删除节点  public void deleteNode(ListNode node){      // 不能为空，不能为尾节点      if (null == node || null == node.next) {          return;      }      node.val = node.next.val;      node.next = node.next.next;  }  </pre>    <h2>2. 逆转单链表</h2>    <p><a href="/misc/goto?guid=4959755644194054792" rel="nofollow,noindex">LeetCode 206. Reverse Linked List</a></p>    <p>题目描述：输出一个单链表的逆序反转后的链表。</p>    <p>分析：非递归的算法很简单，用三个临时指针 prev、cur、next 在链表上循环一遍即可。递归算法是先逆转下一个节点，再逆转当前节点。</p>    <p>下面是两种算法的代码：</p>    <pre>  // 逆转单链表，循环方法  public ListNode reverseByLoop(ListNode head){      if (null == head || null == head.next) {          return head;      }      ListNode prev = null;      ListNode next = null;      // 用 head 作为 cur 指针      while (null != head) {          next = head.next;            head.next = prev;          prev = head;          head = next;      }      return prev;  }    // 逆转单链表，递归方法  public ListNode reverseByRecursion(ListNode head){      // 第一个条件判断异常，第二个条件是结束递归      if (null == head || null == head.next) {          return head;      }        ListNode newHead = reverseByRecursion(head.next);        head.next.next = head;      head.next = null;        return newHead;  }  </pre>    <h2>3. 删除单链表倒数第 n 个节点</h2>    <p><a href="/misc/goto?guid=4959755644282567536" rel="nofollow,noindex">LeetCode 19. Remove Nth Node From End of List</a></p>    <p>题目描述：删除单链表倒数第 n 个节点，1 <= n <= length，尽量在一次遍历中完成。</p>    <p>分析：看到题目时的第一想法是先遍历一次计算出单链表的长度 length，然后在遍历第二次删除第 length - n + 1 个节点，但是这需要遍历两次。正常的删除第 n 个节点只需要遍历一次就可以，如何只遍历一次找到倒数第 n 个节点呢？可以设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，p2 移动到第 n 个节点，然后 p1 和 p2 同时向后移动，当 p2 移动到末尾时，p1 刚好指向倒数第 n 个节点。因为最后要删除倒数第 n 个节点，所以可以找到倒数第 n + 1 个节点，方便删除节点。</p>    <p>代码如下：</p>    <pre>  // 遍历一次，删除单链表倒数第 n 个节点  public ListNode removeNthFromEnd(ListNode head,int n){      if (null == head) {          return head;      }      ListNode p1 = head;      ListNode p2 = head;      // 1. p2 移动到第 n + 1 个节点      for (int i = 0; i < n; i ++>) {          p2 = p2.next;      }      // n == 链表长度时，p2 指向第 n + 1 节点为空，倒数第 n 个节点就是头节点      if (null == p2) {          p1 = head.next;          return p1;      }      // p1 和 p2 同时向后移动，直到 p2 到达尾节点      while (null != p2.next) {          p1 = p1.next;          p2 = p2.next;      }      // 此时 p1 指向倒数第 n + 1 个节点，删除它的下一个节点      p1.next = p1.next.next;      return head;  }  </pre>    <h2>4. 求单链表的中间节点</h2>    <p>题目描述：求单链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。</p>    <p>分析：这道题的思路和第 3 题「删除单链表倒数第 n 个节点」很相似。如果要求只能遍历一遍链表的花，也通过两个指针来完成。两个指针从头节点开始，慢指针每次向后移动一步，快指针每次向后移动两步，直到快指针移动到尾节点时，慢指针移动到中间节点。</p>    <pre>  // 遍历一次，找出单链表的中间节点  public ListNode findMiddleNode(ListNode head){      if (null == head) {          return;      }      ListNode slow = head;      ListNode fast = head;      //如果要求在单链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件      //while(null != fast.next && null != fast.next.next)      while (null != fast && null != fast.next) {          fast = fast.next.next;          slow = slow.next;      }      return slow;  }  </pre>    <h2>5. 判断单链表是否存在环</h2>    <p><a href="/misc/goto?guid=4959755644364097419" rel="nofollow,noindex">LeetCode 141. Linked List Cycle</a></p>    <p>题目描述：判断一个单链表是否有环</p>    <p>分析：还是通过快慢指针来解决，两个指针从头节点开始，慢指针每次向后移动一步，快指针每次向后移动两步，如果存在环，那么两个指针一定会在环内相遇。</p>    <p>代码如下：</p>    <pre>  // 判断单链表是否有环  public boolean hasCycle(ListNode head){      if (null == head) {          return false;      }      ListNode slow = head;      ListNode fast = head;      while (null != fast.next && null != fast.next.next) {          fast = fast.next.next;          slow = slow.next;          if (fast == slow) {              return true;          }      }      return false;  }  </pre>    <h2>6. 单链表是否有环扩展：找到环的入口点</h2>    <p><a href="/misc/goto?guid=4959755644454426665" rel="nofollow,noindex">LeetCode 142. Linked List Cycle II</a></p>    <p>题目描述：判断单链表是否有环，如果有，找到环的入口点</p>    <p>分析：由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让 p2 回到链表的头部，重新走，每次步长不是走 2 了，而是走 1，那么当 p1 和 p2 再次相遇的时候，就是在环路的入口点。</p>    <p>假设起点到环入口的距离尾 a，p1 和 p2 第一次相遇的相交点 M 与环入口的距离为 b，环的周长为 L，当 p1 和 p2 第一次相遇时，假设 p1 走了 n 步。其中 p1 和 p2 第一次相遇时，p1 在环内走过的步数为 b，因为当 p1 走到环入口时，p2 已经在环内了，假设此时 p2 走到环入口的步数为 c，那么 p1 再走 c 步 p2 刚好追上来和 p1 相遇，c < L，所以此时 p1 肯定还没走完一圈。那么根据上面的假设，有下面的关系：</p>    <p>p1 走的路径： a + b = n<br> p2 走的路径： a + b + k * L = 2n ，假设此时 p2 比 p1 多走了 k 圈环路，k >= 1</p>    <p>根据上面的两个等式可以得出 k * L = n = a + b ，那么从相交点 M 开始，p1 再走 a（a = k * L - b） 步，就相当于走了 k 圈，然后回退 b 步，注意环入口到相交点的距离刚好为 b，所以 p1 再走 a 步时到达环入口；而 p2 从头开始走 a 的话也到达了环入口，与 p1 相遇。</p>    <p>而在后面这个步骤中，p1 和 p2 前 a 步走的路径不同，再次相遇时必然在环的入口点。</p>    <p>代码如下：</p>    <pre>  // 找到环的入口点  public ListNode findLoopPort(ListNode head){      if (null == head) {          return null;      }      ListNode p1 = head;      ListNode p2 = head;      boolean hasCycle = false;      // 1. 判断是否有环      while (null != p2.next && null != p2.next.next) {          p1 = p1.next;          p2 = p2.next.next;          if (p1 == p2) {              hasCycle = true;              break;          }      }      if (!hasCycle) {          return null;      }        // p2 从头开始走，步长变为 1      p2 = head;      while (p1 != p2) {          p1 = p1.next;          p2 = p2.next;      }      return p1;  }  </pre>    <h2>7. 判断两个无环单链表是否相交</h2>    <p>题目描述：给出两个无环单链表</p>    <pre>  A:       a1 → a2                   ↘                      c1 → c2 → c3 → null                   ↗              B:  b1 → b2 → b3  </pre>    <p>判断 A 和 B 是否相交。</p>    <p>分析：</p>    <p>1.最直接的方法是判断 A 链表的每个节点是否在 B 链表中，但是这种方法的时间复杂度为 O(Length(A) * Length(B))。</p>    <p>2.转化为环的问题。把 B 链表接在 A 链表后面，如果得到的链表有环，则说明两个链表相交。可以之前讨论过的快慢指针来判断是否有环，但是这里还有更简单的方法。如果 B 链表和 A 链表相交，把 B 链表接在 A 链表后面时，B 链表的所有节点都在环内，所以此时只需要遍历 B 链表，看是否会回到起点就可以判断是否相交。这个方法需要先遍历一次 A 链表，找到尾节点，然后还要遍历一次 B 链表，判断是否形成环，时间复杂度为 O(Length(A) + Length(B))。</p>    <p>3.除了转化为环的问题，还可以利用“如果两个链表相交于某一节点，那么之后的节点都是共有的”这个特点，如果两个链表相交，那么最后一个节点一定是共有的。所以可以得出另外一种解法，先遍历 A 链表，记住尾节点，然后遍历 B 链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。时间复杂度为 O(Length(A) + Length(B))，空间复杂度为 O(1)，思路比解法 2 更简单。</p>    <p>解法 3 的代码如下：</p>    <pre>  // 判断两个无环单链表是否相交  public boolean isIntersect(ListNode headA, ListNode headB){      if (null == headA || null == headB) {          return false;      }      if (headA == headB) {          return true;      }      while (null != headA.next) {          headA = headA.next;      }      while (null != headB.next) {          headB = headB.next;      }      return headA == headB;  }  </pre>    <h2>8. 两个链表相交扩展：判断两个有环单链表是否相交</h2>    <p>题目描述：上面的问题是针对无环链表的，如果是链表有环呢？</p>    <p>分析：如果两个有环单链表相交，那么它们一定共有一个环。因此可以先用之前快慢指针的方式找到两个链表中位于环内的两个节点，如果相交的话，两个节点在一个环内，那么移动其中一个节点，在一次循环内肯定可以与另外一个节点相遇。</p>    <p>代码如下：</p>    <pre>  // 判断两个有环单链表是否相交  public boolean isisIntersectWithLoop(ListNode headA, ListNode headB){      if (null == headA || null == headB) {          return false;      }      if (headA == headB) {          return true;      }      headA = hasCycle(headA);      headB = hasCycle(headB);      // 没有环，则退出      if (null == headA || headB) {          return false;      }        ListNode p = headB.next;      // p 在环内循环一次，直到与 headA 相遇      while (p != headB) {          if (p == headA) {              return true;          }          p = p.next;      }      return false;  }    // 判断单链表是否有环，并返回环内的某一节点  public ListNode hasCycle(ListNode head){      if (null == head) {          return null;      }      ListNode slow = head;      ListNode fast = head;      while (null != fast.next && null != fast.next.next) {          fast = fast.next.next;          slow = slow.next;          if (fast == slow) {              return slow;          }      }      return null;  }  </pre>    <h2>9. 两个链表相交扩展：求两个无环单链表的第一个相交点</h2>    <p><a href="/misc/goto?guid=4959755644532276551" rel="nofollow,noindex">LeetCode 160. Intersection of Two Linked Lists</a></p>    <p>题目描述：找到两个无环单链表第一个相交点，如果不相交返回空，要求在线性时间复杂度和常量空间复杂度内完成。</p>    <p>分析：</p>    <p>下面所说的对齐：表示指针到链表末尾的距离相同。</p>    <p>1.分为先判断是否有环，再求第一个相交点的方式。分别遍历 A 链表和 B 链表，判断它们的最后一个节点是否相交。然后利用对齐的思想，计算两个链表的长度（这个可以放在之前的遍历中做），分别用 p1 和 p2 指向两个链表的头，然后将较长链表的 p1 (假设为 p1)向后移动 LB - LA 个节点。这样 p1 和 p2 对齐了，然后同时向后移动 p1 和 p2，直到 p1 == p2 ，相遇的点就是第一个节点。</p>    <p>2.解法 1 中为了对齐需要计算链表的长度，有没有什么方法可以不用计算链表长度呢？假设 A 链表和 B 链表的长度为 LA 和 LB，假设 LB >= LA，两个指针 p1 和 p2 分别指向 A 链表和 B 链表的头节点。同时向后移动，当 p1 移动 A 链表的末尾时，p2 距离 B 链表的末尾的距离为 LB - LA ，此时可以看出我们已经得到了长度差，如何利用这个长度差对齐呢。这时将 p1 移动到 B 链表的头部，两个指针继续移动，当 p2 移动到 B 链表的末尾时，p1 刚好移动了 LB - LA 步。此时再将 p2 移动到 A 链表的头部，这样 p1 和 p2 就对齐了，然后继续移动，直到 p1 == p2 。如果两个链表不相交，p1 和 p2 移动会同时移动到末尾都指向空，而相交的话，第一次相等时就是第一个相交点。这种方法的时间复杂度为 O (2 * (Length(B)))，最多要遍历两次长度较长的链表。</p>    <p>解法 2 的代码如下：</p>    <pre>  // 求两个无环单链表的第一个相交点  public ListNode getIntersectionNode(ListNode headA, ListNode headB){      if (null == headA || null == headB) {          return null;      }      if (headA == headB) {          return headA;      }        ListNode p1 = headA;      ListNode p2 = headB;      while (p1 != p2) {          // 遍历完所在链表后从另外一个链表再开始          // 当 p1 和 p2 都换到另一个链表时，它们对齐了：          // （1）如果链表相交，p1 == p2 时为第一个相交点          // （2）如果链表不相交，p1 和 p2 同时移动到末尾，p1 = p2 = null，然后退出循环          p1 = (null == p1) ? headB : p1.next;          p2 = (null == p2) ? headA : p2.next;      }      return p1;  }  </pre>    <p> </p>    <p>来自：http://johnnyshieh.me/posts/interview-linked-list/</p>    <p> </p>