面试时，链表解题方法论：
1、对于笔试， 不用太在乎空间复杂度，一切为了时间复杂度
2、对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

链表面试题常用数据结构和技巧

1、使用容器（哈希表、数组等）
2、快慢指针

1）输入链表头结点，奇数长度返回中点，偶数长度返回上中点

  1. /**
  2.  * 快慢指针从头出发，都从奇数位开始走
  3.  * 这样快指针每次走两步后都在奇数位上
  4.  * 这样在偶数长度链表上，当快指针不能往下走的时候，慢指针正好在上中点
  5.  */
  6. public Node midOrUpMidNode(Node head) {
  7.     if (head == null || head.next == null) {
  8.         return head;
  9.     }
  10.       //慢指针
  11.     Node slow = head;
  12.       //快指针
  13.     Node fast = head;
  14.     while (fast.next != null && fast.next.next != null) {
  15.         slow = slow.next;
  16.         fast = fast.next.next;
  17.     }
  18.     return slow;
  19. }

2）输入链表头结点，奇数长度返回中点，偶数长度返回下中点

  1. /**
  2.  * 快慢指针从第二个结点出发，都从偶数位开始走
  3.  * 这样快指针每次走两步后都在偶数位上
  4.  * 这样在偶数长度链表上，当快指针不能往下走的时候，慢指针正好在下中点
  5.  */
  6. public Node midOrDownMidNode(Node head) {
  7.     if (head == null || head.next == null) {
  8.         return head;
  9.     }
  10.     Node slow = head.next;
  11.     Node fast = head.next;
  12.     while (fast.next != null && fast.next.next != null) {
  13.         slow = slow.next;
  14.         fast = fast.next.next;
  15.     }
  16.     return slow;
  17. }

3）输入链表头结点，奇数长度返回中点前一个，偶数长度返回上中点前一个

  1. public Node findMid(Node head) {
  2.     if (head == null || head.next == null || head.next.next == null) {
  3.         return head;
  4.     }
  5.     Node slow = head;
  6.     Node fast = head.next.next;
  7.     while (fast.next != null && fast.next.next != null) {
  8.         slow = slow.next;
  9.         fast = fast.next.next;
  10.     }
  11.     return slow;
  12. }

4）输入链表头结点，奇数长度返回中点前一个，偶数长度返回下中点前一个

  1. public Node findMid(Node head) {
  2.     if (head == null || head.next == null) {
  3.         return null;
  4.     }
  5.     if (head.next.next == null) {
  6.         return head;
  7.     }
  8.     Node slow = head;
  9.     Node fast = head.next;
  10.     while (fast.next != null && fast.next.next != null) {
  11.         slow = slow.next;
  12.         fast = fast.next.next;
  13.     }
  14.     return slow;
  15. }

常见面试题

1）给定一个单链表的头结点head，请判断该链表是否为回文结构。

  1. public boolean isPalindrome1(Node head) {
  2.     Stack<Node> stack = new Stack<Node>();
  3.     Node cur = head;
  4.     while (cur != null) {
  5.         stack.push(cur);
  6.         cur = cur.next;
  7.     }
  8.     while (head != null) {
  9.         if (head.value != stack.pop().value) {
  10.             return false;
  11.         }
  12.         head = head.next;
  13.     }
  14.     return true;
  15. }
  1. //实现思路
  2. //1.先找出中点（偶数个是找出上中点）
  3. //2.将中点的下个节点指向空，从中点的下个节点开始反转列表
  4. //3.然后从新链表的头和原链表的头开始遍历链表并比较，全部相等则是回文，否则不是
  5. //4.恢复原链表结构（将反转的链表再次反转为原始状态）
  6. // need O(1) extra space
  7. public static boolean isPalindrome3(Node head) {
  8.     if (head == null || head.next == null) {
  9.         return true;
  10.     }
  11.     Node n1 = head;
  12.     Node n2 = head;
  13.     while (n2.next != null && n2.next.next != null) { // find mid node
  14.         n1 = n1.next; // n1 -> mid
  15.         n2 = n2.next.next; // n2 -> end
  16.     }
  17.     // n1 中点
  20.     n2 = n1.next; // n2 -> right part first node
  21.     n1.next = null; // mid.next -> null
  22.     Node n3 = null;
  23.     while (n2 != null) { // right part convert
  24.         n3 = n2.next; // n3 -> save next node
  25.         n2.next = n1; // next of right node convert
  26.         n1 = n2; // n1 move
  27.         n2 = n3; // n2 move
  28.     }
  29.     n3 = n1; // n3 -> save last node
  30.     n2 = head;// n2 -> left first node
  31.     boolean res = true;
  32.     while (n1 != null && n2 != null) { // check palindrome
  33.         if (n1.value != n2.value) {
  34.             res = false;
  35.             break;
  36.         }
  37.         n1 = n1.next; // left to mid
  38.         n2 = n2.next; // right to mid
  39.     }
  40.     n1 = n3.next;
  41.     n3.next = null;
  42.     while (n1 != null) { // recover list
  43.         n2 = n1.next;
  44.         n1.next = n3;
  45.         n3 = n1;
  46.         n1 = n2;
  47.     }
  48.     return res;
  49. }

2）将单项链表按某值划分成左边小、中间相等、右边大的形势

  1. public static Node listPartition1(Node head, int pivot) {
  2.     if (head == null) {
  3.         return head;
  4.     }
  5.     Node cur = head;
  6.     int i = 0;
  7.     while (cur != null) {
  8.         i++;
  9.         cur = cur.next;
  10.     }
  11.     Node[] nodeArr = new Node[i];
  12.     i = 0;
  13.     cur = head;
  14.     for (i = 0; i != nodeArr.length; i++) {
  15.         nodeArr[i] = cur;
  16.         cur = cur.next;
  17.     }
  18.     arrPartition(nodeArr, pivot);
  19.     for (i = 1; i != nodeArr.length; i++) {
  20.         nodeArr[i - 1].next = nodeArr[i];
  21.     }
  22.     nodeArr[i - 1].next = null;
  23.     return nodeArr[0];
  24. }
  26. public static void arrPartition(Node[] nodeArr, int pivot) {
  27.     int small = -1;
  28.     int big = nodeArr.length;
  29.     int index = 0;
  30.     while (index != big) {
  31.         if (nodeArr[index].value < pivot) {
  32.             swap(nodeArr, ++small, index++);
  33.         } else if (nodeArr[index].value == pivot) {
  34.             index++;
  35.         } else {
  36.             swap(nodeArr, --big, index);
  37.         }
  38.     }
  39. }
  1. public static Node listPartition2(Node head, int pivot) {
  2.     Node sH = null; // small head
  3.     Node sT = null; // small tail
  4.     Node eH = null; // equal head
  5.     Node eT = null; // equal tail
  6.     Node mH = null; // big head
  7.     Node mT = null; // big tail
  8.     Node next = null; // save next node
  9.     // every node distributed to three lists
  10.     while (head != null) {
  11.         next = head.next;
  12.         head.next = null;
  13.         if (head.value < pivot) {
  14.             if (sH == null) {
  15.                 sH = head;
  16.                 sT = head;
  17.             } else {
  18.                 sT.next = head;
  19.                 sT = head;
  20.             }
  21.         } else if (head.value == pivot) {
  22.             if (eH == null) {
  23.                 eH = head;
  24.                 eT = head;
  25.             } else {
  26.                 eT.next = head;
  27.                 eT = head;
  28.             }
  29.         } else {
  30.             if (mH == null) {
  31.                 mH = head;
  32.                 mT = head;
  33.             } else {
  34.                 mT.next = head;
  35.                 mT = head;
  36.             }
  37.         }
  38.         head = next;
  39.     }
  40.     // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
  41.     if (sT != null) { // 如果有小于区域
  42.         sT.next = eH;
  43.         eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
  44.     }
  45.     // 下一步，一定是需要用eT 去接 大于区域的头
  46.     // 有等于区域，eT -> 等于区域的尾结点
  47.     // 无等于区域，eT -> 小于区域的尾结点
  48.     // eT 尽量不为空的尾巴节点
  49.     if (eT != null) { // 如果小于区域和等于区域，不是都没有
  50.         eT.next = mH;
  51.     }
  52.     return sH != null ? sH : (eH != null ? eH : mH);
  53. }

3）一种特殊的单链表节点类描述如下，给定一个由Node节点类型组成的无环单链表的头结点head，请实现一个函数完成这个链表的复制，并返回复制的新链表头节点。要求时间复杂度O(N)，额外空间复杂度O(1)

class Node { int value; Node next; Node rand; Node(int val) {value = val;} }

  1. public static Node copyListWithRand1(Node head) {
  2.     if (head == null) {
  3.         return null;
  4.     }
  5.     Map<Node, Node> cloneMap = new HashMap<>();
  6.     Node node = head;
  7.     while (node != null) {
  8.         cloneMap.put(node, new Node(node.value));
  9.         node = node.next;
  10.     }
  12.     node = head;
  13.     while (node != null) {
  14.         cloneMap.get(node).next = cloneMap.get(node.next);
  15.         cloneMap.get(node).rand = cloneMap.get(node.rand);
  16.         node = node.next;
  17.     }
  18.     return cloneMap.get(head);
  19. }
  1. public static Node copyRandomList2(Node head) {
  2.     if (head == null) {
  3.         return null;
  4.     }
  5.     Node cur = head;
  6.     Node next = null;
  7.     // 1 -> 2 -> 3 -> null
  8.     // 1 -> 1' -> 2 -> 2' -> 3 -> 3'
  9.     while (cur != null) {
  10.         next = cur.next;
  11.         cur.next = new Node(cur.val);
  12.         cur.next.next = next;
  13.         cur = next;
  14.     }
  15.     cur = head;
  16.     Node copy = null;
  17.     // 1 1' 2 2' 3 3'
  18.     // 依次设置 1' 2' 3' random指针
  19.     while (cur != null) {
  20.         next = cur.next.next;
  21.         copy = cur.next;
  22.         copy.random = cur.random != null ? cur.random.next : null;
  23.         cur = next;
  24.     }
  25.     Node res = head.next;
  26.     cur = head;
  27.     // 老 新 混在一起，next方向上，random正确
  28.     // next方向上，把新老链表分离
  29.     while (cur != null) {
  30.         next = cur.next.next;
  31.         copy = cur.next;
  32.         cur.next = next;
  33.         copy.next = next != null ? next.next : null;
  34.         cur = next;
  35.     }
  36.     return res;
  37. }

4）给定两个可能有环也可能无环的单链表，头结点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点，如果不相交，返回null。【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

  1. public static Node getIntersectNode1(Node head1, Node head2) {
  2.     if (head1 == null || head2 == null) {
  3.         return null;
  4.     }
  5.     Set<Node> set1 = new HashSet<>();
  6.     Node curr = head1;
  7.     while (curr != null && !set1.contains(curr)) {
  8.         set1.add(curr);
  9.         curr = curr.next;
  10.     }
  12.     Set<Node> set2 = new HashSet<>();
  13.     curr = head2;
  14.     while (curr != null && !set2.contains(curr)) {
  15.         if (set1.contains(curr)) {
  16.             return curr;
  17.         }
  18.         set2.add(curr);
  19.         curr = curr.next;
  20.     }
  21.     return null;
  22. }
  1. //主函数
  2. public static Node getIntersectNode(Node head1, Node head2) {
  3.     if (head1 == null || head2 == null) {
  4.         return null;
  5.     }
  6.     //分别找出两个链表的第一个入环结点
  7.     Node loop1 = getLoopNode(head1);
  8.     Node loop2 = getLoopNode(head2);
  9.     //两个链表无环，可能相交（在某个结点相遇后，后续部分公用），可能不相交
  10.     if (loop1 == null && loop2 == null) {
  11.         return noLoop(head1, head2);
  12.     }
  13.     //两个链表有环，可能不相交，如果相交存在两种情况
  14.     //1、在同一个结点入环，相交结点一个
  15.     //2、不同的结点入环，相交结点两个（返回任一相交结点）
  16.     if (loop1 != null && loop2 != null) {
  17.         return bothLoop(head1, loop1, head2, loop2);
  18.     }
  19.     //一个有环一个无环，不可能相交
  20.     return null;
  21. }
  23. // 找到链表第一个入环节点，如果无环，返回null
  24. // 隐藏技巧：快慢指针第一次相遇后，快指针回到头结点，然后快慢指针每次都走一步，最后相遇结点一定是入环结点
  25. public static Node getLoopNode(Node head) {
  26.     if (head == null || head.next == null || head.next.next == null) {
  27.         return null;
  28.     }
  29.     // n1 慢  n2 快
  30.     Node slow = head.next; // n1 -> slow
  31.     Node fast = head.next.next; // n2 -> fast
  32.     while (slow != fast) {
  33.         if (fast.next == null || fast.next.next == null) {
  34.             return null;
  35.         }
  36.         fast = fast.next.next;
  37.         slow = slow.next;
  38.     }
  39.     // slow fast  相遇
  40.     fast = head; // n2 -> walk again from head
  41.     while (slow != fast) {
  42.         slow = slow.next;
  43.         fast = fast.next;
  44.     }
  45.     return slow;
  46. }
  48. // 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
  49. public static Node noLoop(Node head1, Node head2) {
  50.     if (head1 == null || head2 == null) {
  51.         return null;
  52.     }
  53.     Node cur1 = head1;
  54.     Node cur2 = head2;
  55.     int n = 0;
  56.     while (cur1.next != null) {
  57.         n++;
  58.         cur1 = cur1.next;
  59.     }
  60.     while (cur2.next != null) {
  61.         n--;
  62.         cur2 = cur2.next;
  63.     }
  64.     if (cur1 != cur2) {
  65.         return null;
  66.     }
  67.     // n  :  链表1长度减去链表2长度的值
  68.     cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
  69.     cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
  70.     n = Math.abs(n);
  71.     while (n != 0) {
  72.         n--;
  73.         cur1 = cur1.next;
  74.     }
  75.     while (cur1 != cur2) {
  76.         cur1 = cur1.next;
  77.         cur2 = cur2.next;
  78.     }
  79.     return cur1;
  80. }
  82. // 两个有环链表，返回第一个相交节点，如果不相交返回null
  83. public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
  84.     Node cur1 = null;
  85.     Node cur2 = null;
  86.     if (loop1 == loop2) {
  87.         cur1 = head1;
  88.         cur2 = head2;
  89.         int n = 0;
  90.         while (cur1 != loop1) {
  91.             n++;
  92.             cur1 = cur1.next;
  93.         }
  94.         while (cur2 != loop2) {
  95.             n--;
  96.             cur2 = cur2.next;
  97.         }
  98.         cur1 = n > 0 ? head1 : head2;
  99.         cur2 = cur1 == head1 ? head2 : head1;
  100.         n = Math.abs(n);
  101.         while (n != 0) {
  102.             n--;
  103.             cur1 = cur1.next;
  104.         }
  105.         while (cur1 != cur2) {
  106.             cur1 = cur1.next;
  107.             cur2 = cur2.next;
  108.         }
  109.         return cur1;
  110.     } else {
  111.         cur1 = loop1.next;
  112.         while (cur1 != loop1) {
  113.             if (cur1 == loop2) {
  114.                 return loop1;
  115.             }
  116.             cur1 = cur1.next;
  117.         }
  118.         return null;
  119.     }
  120. }
  1. //使用方法
  2. Node[] nodes = generateRandomLinkedList(len, val);
  3. Node intersectNode1 = nodes[2];
  4. Node intersectNode2 = nodes[3];
  5. Node intersectNode = getIntersectNode(nodes[0], nodes[1]);
  6. if (intersectNode1 == null && intersectNode != null) {
  7.     throw new RuntimeException("error");
  8. }
  9. if (intersectNode1 != null && intersectNode != intersectNode1 
  10.     && intersectNode != intersectNode2) {
  11.     throw new RuntimeException("error");
  12. }
  14. // for test 生成随机长度的相交或不相交链表并返回相交结点(有相交的情况)
  15. // 返回数组第一个为链表1的头结点
  16. // 第二个为链表2的头结点
  17. // 第三个为第一个相交的结点（只有一个相交结点时也在此返回）
  18. // 第四个为第二个相交的结点（只有真实存在两个相交结点时才返回）
  19. private static Node[] generateRandomLinkedList(int len, int maxValue) {
  20.     int length1 = (int) (Math.random() * len) + 1;
  21.     Node[] arr1 = new Node[length1];
  22.     for (int i = 0; i < length1; i++) {
  23.         arr1[i] = new Node((int) (Math.random() * maxValue) + 1);
  24.     }
  26.     int length2 = (int) (Math.random() * len) + 1;
  27.     Node[] arr2 = new Node[length2];
  28.     for (int i = 0; i < length2; i++) {
  29.         arr2[i] = new Node((int) (Math.random() * maxValue) + 1);
  30.     }
  31.     for (int i = 0; i < arr1.length - 1; i++) {
  32.         if (i < length1 - 1) {
  33.             arr1[i].next = arr1[i + 1];
  34.         }
  35.     }
  36.     Node intersect1 = null;
  37.     Node intersect2 = null;
  38.     switch ((int) ((Math.random() * 5)) + 1) {
  39.         case 1: //两个无环链表无相交
  40.             for (int i = 0; i < arr2.length; i++) {
  41.                 if (i < length2 - 1) {
  42.                     arr2[i].next = arr2[i + 1];
  43.                 }
  44.             }
  45.             System.out.println("两个无环链表无相交");
  46.             break;
  47.         case 2: //两个无环链表相交
  48.             int i1 = (int) (Math.random() * length1);
  49.             int i2 = (int) (Math.random() * length2);
  50.             for (int i = 0; i < arr2.length; i++) {
  51.                 if (i < length2 - 1) {
  52.                     arr2[i].next = arr2[i + 1];
  53.                 }
  54.                 if (i == i2) {
  55.                     arr2[i].next = arr1[i1];
  56.                     break;
  57.                 }
  58.             }
  59.             intersect1 = arr1[i1];
  60.             System.out.println("两个无环链表相交");
  61.             break;
  62.         case 3: //一个有环链表一个无环链表，不存在相交
  63.             for (int i = 0; i < arr2.length; i++) {
  64.                 if (i < length2 - 1) {
  65.                     arr2[i].next = arr2[i + 1];
  66.                 }
  67.             }
  68.             i2 = (int) (Math.random() * length2);
  69.             arr2[arr2.length - 1].next = arr2[i2];
  70.             System.out.println("一个有环链表一个无环链表，不存在相交");
  71.             break;
  72.         case 4: //两个有环链表无相交
  73.             i1 = (int) (Math.random() * length1);
  74.             arr1[arr1.length - 1].next = arr1[i1];
  76.             for (int i = 0; i < arr2.length; i++) {
  77.                 if (i < length2 - 1) {
  78.                     arr2[i].next = arr2[i + 1];
  79.                 }
  80.             }
  81.             i2 = (int) (Math.random() * length2);
  82.             arr2[arr2.length - 1].next = arr2[i2];
  83.             System.out.println("两个有环链表无相交");
  84.             break;
  85.         case 5: //两个有环链表相交
  86.             i1 = (int) (Math.random() * length1);
  87.             i2 = (int) (Math.random() * length2);
  88.             for (int i = 0; i < arr2.length; i++) {
  89.                 if (i < length2 - 1) {
  90.                     arr2[i].next = arr2[i + 1];
  91.                 }
  92.                 if (i == i2) {
  93.                     arr2[i].next = arr1[i1];
  94.                     break;
  95.                 }
  96.             }
  97.             if (arr2[i2].next == null) {
  98.                 System.out.println();
  99.             }
  100.             intersect1 = arr1[i1];
  101.             i1 = (int) (Math.random() * length1);
  102.             arr1[arr1.length - 1].next = arr1[i1];
  103.             intersect2 = arr1[i1];
  104.             System.out.println("两个有环链表相交");
  105.     }
  107.     return new Node[]{arr1[0], arr2[0], intersect1, intersect2};
  108. }
  110. private static class Node {
  111.     int value;
  112.     Node next;
  114.     public Node(int value) {
  115.         this.value = value;
  116.     }
  118.     @Override
  119.     public String toString() {
  120.         return "Node{" + "value=" + value + '}';
  121.     }
  122. }

5）能不能不给单链表的头结点，只给想要删除的结点，就能做到在链表上把这个点删掉？

此题有问题，（错误解法，将下个节点的值设置到给定的节点）无法删除末尾节点。 要删除指定的node还是需要给头结点。