1.打印两个有序链表的公共部分
【题目】给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。例如：
【思路】因为链表有序，两个指针同时开始，一一进行比较，谁小谁就往后移动，若相等就打印，然后一起向后移动。
2.判断一个链表是否为回文结构
【题目】给定一个链表的头节点head，请判断该链表是否为回文结构。例如：
1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。
【思路】
- 方法一：遍历链表，将值依次入栈，因为回文就是正序遍历=逆序遍历；再次遍历链表，同时栈依次弹出，如果一直都是相等的，就是回文。
- 方法二：（栈的空间减少了一半）两个指针，一快一慢，即一个走一步，一个走两步；当快指针走完之后，慢指针在此之后遍历的数字依次入栈；然后再次从头遍历指针，同时栈依次弹出，如果一直都是相等的，就是回文。
【进阶】如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
【思路】两个指针，一快一慢，即一个走一步，一个走两步；当快指针走完之后，慢指针在此之后遍历的数字进行reverse；然后从两头同时开始遍历，如果一直都是相等的，就是回文。
3.将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】
- 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。
- 实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。除这个要求外，对调整后的节点顺序没有更多的要求。
- 例如：链表9->0->4->5->1，pivot=3。调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。
- 总之，满足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。
【思路】
- 需要考虑某一块没有的情况。
- 方法一：准备三个队列，遍历链表，将节点入相应的队列中，然后再依次出队列即可。
- 方法二：遍历链表，分别找到第一个小于、等于和大于pivot的节点；然后将三个节点分别作为头结点，遇到相应的节点就放入其中；最后将三个链表的首尾相连即可。
4.复制含有随机指针节点的链表
【题目】一种特殊的链表节点类描述如下：
public class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
- Node类中的value是节点值，next指针和正常单链表中next指针的意义一样，都指向下一个节点，rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。
- 给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。
【进阶】不使用额外的数据结构，只用有限几个变量，且在时间复杂度为O(N)内完成原问题要实现的函数。
【思路】
- 方法一：经典解法，用map
- 方法二：克隆节点的时候，就将其放在老节点的后面，克隆节点的random指向相对应老节点的random.next。然后进行分离，得到克隆链表，分离的时候不需要考虑random指针。
5.两个单链表相交的一系列问题
【题目】
- 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。
- 请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null即可。
【要求】如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。
【思路】
- 判断链表是否有环，如果有环，返回第一个入环的节点。
- 方法一：遍历链表，将每个节点加入到map里，如果发现有一个节点再加入map前就已经存在于map中，说明有环，该节点即为入环节点；如果最后走到null了，说明无环。
- 方法二：两个指针，一快一慢，即一个走一步，一个走两步。如果无环，那么快指针一定会走到结尾；如果有环，那么快指针和慢指针一定会在环里相遇，相遇后，快指针回到head节点，然后快指针和慢指针都变为每次走一步，同时开始走，一定会在入环节点相遇（数学结论）。
- 二者相交分为三种情况
- 情况一：两个单链表都无环。首先获取两个链表的长度，求得差值；用两个指针，长度长的链表指针先走差值的步数，然后再同时走；如果last1=last2说明它们一定相交，否则不相交。
- 情况二：一个链表有环，一个链表无环，绝对不可能相交。因为一个节点只能有一个next。
- 情况三：两个链表都有环。
- 两个链表在环出现之前就相交了，之后一直相交。loop1=loop2，即两个链表的入环节点相同，则相交。用两个指针，长度长的链表指针先走差值的步数，然后再同时走；如果两个链表的入环节点都不为空且相等，则相交。
- 两个链表只共享环。loop1在环中走的时候遇到了loop2，但不相等。
6.反转单向和双向链表
【题目】分别实现反转单向链表和反转双向链表的函数。
【要求】如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)。
【思路】可以用栈或者原地反转。
网友评论