从尾到头打印链表
Q：不希望打印时修改内容，怎么办？
A：遍历的时候从头到尾，而输出的顺序是从尾到头，典型的“后进先出”，用一个栈来模拟一下即可（java）。
删除链表中重复的节点
A：从头遍历整个链表。如果当前节点的值与下一个节点的值相同，那它们就是重复节点，都可以被删除。为了保证删除后的链表仍然是相连的，我们要把当前节点的前一个节点（pre）和后面值比当前节点的值大的节点相连。我们要确保（pre）始终与下一个没有重复的节点连接在一起（c++）。
链表中环的入口节点
A：依然是用两个指针来解决
有两个结论：
1，设置快慢指针，如果有环，最后一定会相遇；
2，两个指针从链表头和相遇点相继出发，每次走一步，最后一定相遇于环入口（java）。
链表中倒数第k个节点
A：假设整个链表有n个节点，那么，倒数第k个节点就是从头节点开始的第n-k+1个节点。从这个想法为基础，继续脑洞大开。
为了只遍历链表一次就找到倒数第k个节点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针不动；从第k步开始，第二个指针也开始从动。由于两个指针的距离保持在k-1，当第一个指针到达链表的尾节点时，第二个指针刚好到达倒数第k个节点（java）。
反转链表
A：（看上去好简单，但千万不能掉以轻心）
比如这些问题考虑了吗——输入的链表头指针为nullptr或者整个链表只有一个节点；反转后的链表是否断裂；返回的反转之后的头节点是不是原始链表的尾节点？
提示：定义三个指针，分别指向当前遍历到的节点，它的前一个节点及后一个节点（java）。
合并两个排序的链表
A：这是容易见到的面试题，容易犯的错误有：一是没想清楚合并的过程，最终合并后的链表要么断开，要么没有递增排序；二是鲁棒性存在问题，一旦有特殊的输入（如空链表）就崩了。
提示：合并前的比较+递归（java）。
两个链表的第一个公共节点
A：暴力遍历前，先分析一下，
从链表节点的定义看，这两个链表是单向链表。如果两个链表有公共节点，那么，这两个链表从某一个节点开始，它们的m_pNext都指向同一个节点。也就是说，两个链表有部分重合的链表，其拓扑形状看起来像是一个Y，而不可能是X。
可想而知，我们可以从链表的尾部开始遍历，嘿嘿，看过上面的题目，自然想到要用辅助栈——分别把两个链表的节点放入两个栈里，接下来比较两个栈顶的节点是否相同。如果相同，则把栈顶弹出接着比较下一个栈顶，直至找到最后一个相同的节点（java）。
复杂链表的复制
A：有两种办法 （前一种用空间换时间，后一种更巧妙）
1，先复制原始链表上的每个节点N创建N‘，然后把这些创建出来的节点有m_pNext链接起来，同时我们把<N,N'>的配对信息放到一个哈希表中；第二步还是设置复制链表上每个节点的m_pSibling。如果在原始链表中节点N的m_pSibling指向节点S，那么在复制链表中，对应的N’应该指向S‘。由于有了哈希表，我们可以用O(1)的时间根据S找到S’。
2，（1）仍然是根据原始链表的每个节点N创建对应的N‘，但这一次，把N’链接在N的后面；（2）设置复制出来的节点的m_pSibling，按图索骥就行；（3）拆链 。
（java）
网友评论