链表

单链表

双链表

换头问题

1. 带返回值返回新地址
2. 头节点刷新一遍内容
3. 一个特殊的头部节点

题（链表题）

打印有序链表公共部分（双指针）

• 题
  • 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分 (要求如果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1))
• 答案
  • 非常非常基础，自己做。类似归并排序的过程，双指针就行

单链表回文结构（快慢指针、改数据结构 - 单链表逆序!）

• 题
  • 判断一个链表是否为回文结构
  • 给定一个单链表的头节点head，请判断该链表是否为回文结构。 例子：1->2->1，返回true; 1->2->2->1，返回true; 15->6->15，返回true;1->2->3，返回false。 (如果链表长度为N，时间复杂度达到0(N)，额外空间复杂度达到O(1)
• 答案
  • 也很简单。栈可以实现，但空间复杂度O(N)。
    • 优化：只压一般栈。那怎么实现只压一半的栈（在没有缓存大小的情况）
    • 使用快慢指针，快指针一次两步，慢指针一次一步，当快到达终点后，慢指针就到达中间了
  • 但如果空间复杂度是O(1)，双链表直接双指针。但题目又要求单链表，想不出
  • 答案：双指针往中间！慢指针将中间往后一半进行单链表的逆序！然后就形成了一个类似双链表的东西，就可以用双指针了，判断完将他恢复回去就行

将单向链表按某值划分成左边小、中间相等、右边大的形式

• 题
  • 给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。 实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
  • 也就是说单链表版的快速排序的第一部分
• 一些要求
  • [要求] 调整后所有小于pivot的节点之间的相对顺序和调整前一样
  • [要求] 调整后所有等于pivot的节点之间的相对顺序和调整前
  • [要求] 调整后所有大于pivot的节点之间的相对顺序和调整前
  • [要求] 时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
• 答案
  • 6个变量：SmallHeader、SmallTail、EqualHeader、EqualTail、BigHeader、BigTail
  • 遍历链表：小于5的放左边两个，等于5的放中间两个，大于5的放右边两个，这三个部分内部互连
  • 最后再连接这三个部分就完成了。SH -> ... -> ST -> EH -> ... -> ET -> BH -> ... -> BT
  • 注意最好要考虑好边界，例如这三部分可能有一部分是没数据的

复制含有随机指针节点的链表 (链表改拓扑形成哈希表)

• 题：

  • 一种特殊的单链表节点类描述如下

    class Node {
    	int value;
    	Node next;
    	Node rand;	// rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null
    	Node(int val) [
    		value = val;
    	}
    }
    

    给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点

  • [要求] 时间复杂度O(N)，额外空间复杂度O(1)

• 答案：

  • 如果用额外空间就很简单，用哈希表就行。准备一个哈希表，存储：key(老节点):value(新节点)，N个老节点就创建N个新节点并往UnorderHashMap里塞如N组Key-Value

  • 不用额外空间的做法：

    篡改原数组，进行全插入：Node1Old -> Node1New -> Node2Old -> Node2New -> …… 这个时候其实也相当于有一个天然的哈希表来映射 NodeOlds 和 NodeNews

找链表环点 (很难想到，快慢指针+双指针找入环点)

先来看怎么判断一个链表的环？

• O(N)：可以用hash表。遍历时一直放节点地址到hashMap里，直到发现新的节点在hashMap里

• O(1)：很妙

  • 先用快慢指针让两者相遇。例如环外5个位置，环内4的节点，快指针2步慢指针1步。最后快慢指针一定会在环内相遇！

    （并且快慢指针运行的圈数不会大于2。最简单的证明和理解是：当快指针和慢指针都在环内时，快指针在追赶慢指针，且两者的距离每次减一）

  • 然后再指针找入环节点。我们将快指针去掉并在链头放一个新指针指针，慢指针位置不变。然后两个指针每次移动一，最后会在入环节点处相遇 简单证明：

    $$t1=第一次步数或距离，t2=第二次步数或距离，L_外=环外长度，L_内=环内长度，k为任意圈\\ ~\\ 第一次步骤有：\\ t1=L_外+k_1*L_内\\ 2t1=L_外+k_2*L_内\\ t1=k_3*L内\\ ~\\ 第二次时，t2=L_外\\ 有t_2 = t_{1+2}-k_4*L_内$$

两个单链表相交的一系列问题 (情况很多)

“单链表算法层次上最难的题，没有之一。而且可以做到空间O(1)”

• 题
  • 给定两个可能有环也可能无环的单链表，头节点head1和head2。 请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null
  • 要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
• 答案
  • 这里分有环和无环的情况
  • 均无环判断相交
    • 由于单链表只指向一个地址，无环的化形状大概像“Y”型 (不可能是"X"型，链表只有一个next指针)。
    • 判断end节点的地址是否相同，如是则相交。
    • 找相交节点
      • 我刚开始想的是：可以逆序链表然后往后遍历，逆序的过程中遇到冲突了，那就是相交的位置了
      • 但其实更简单：第一次判断end节点时，已经都两条链表各自的长度L1和L2了，例如分别100和80，那么1走20步，然后两边同步指针一起走就行
  • 一边有环判断相交
    • 这种情况不可能出现。简单思想证明： 假如L1和L2无环相交，即"Y"型。此时如果L1有环则遍历的最后一个节点指回自身，相当于 "Y" 型的下面又链回自己，此时另一节点一定有环
  • 均有环判断相交
    • 一共三种情况：
      • 情况一：两个链表不相交，各自为环
      • 情况二：入环点是同一个，相当于"Y"下面的部分反过来接到三叉点的下部
      • 情况三：入环点不是同一个，相当于"Y"下面的部分反过来接到三叉点的上部（左上或右上）。或可以想像成一个环的基础上两个不同位置上的点往外延伸，可能更形象点
    • 分别解决
      • 情况二：最简单，各自找入环地址，如果发现相同就是情况二
      • 情况一/三：都找到入环地址后，一个入环继续走，看他能不能遇到另一个入环地址。若能则是情况三，否则是情况一

解题思维总结

链表相关的题几乎都没有算法题，都是coding题

面试时链表解题的方法论

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

重要技巧:

1. 额外数据结构记录 (哈希表等)
2. 快慢指针 (例如快指针2步慢指针一步，也是双指针的一种，快慢指针有时不同的定制)
3. 空间限制O(1)时，经常需要篡改原来的数据结构的拓扑，如：
   • 链表的逆序 (回文判断题)
   • 链表全插入 (含随机节点的链表复制题)
   • 拓扑形成额外信息表 (含随机节点的链表复制题，既然不让创建哈希表，我就让链表本身形成类似哈希表的结构)