链表系列题目

【题目】给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。例如：
【思路】因为链表有序，两个指针同时开始，一一进行比较，谁小谁就往后移动，若相等就打印，然后一起向后移动。

【题目】给定一个链表的头节点head，请判断该链表是否为回文结构。例如：
1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。
【思路】

方法一：遍历链表，将值依次入栈，因为回文就是正序遍历=逆序遍历；再次遍历链表，同时栈依次弹出，如果一直都是相等的，就是回文。
方法二：（栈的空间减少了一半）两个指针，一快一慢，即一个走一步，一个走两步；当快指针走完之后，慢指针在此之后遍历的数字依次入栈；然后再次从头遍历指针，同时栈依次弹出，如果一直都是相等的，就是回文。

【进阶】如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
【思路】两个指针，一快一慢，即一个走一步，一个走两步；当快指针走完之后，慢指针在此之后遍历的数字进行reverse；然后从两头同时开始遍历，如果一直都是相等的，就是回文。

【题目】

给定一个单向链表的头节点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的节点即可。对某部分内部的节点顺序不做要求。

【思路】

【题目】一种特殊的链表节点类描述如下：

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指针。

【题目】

【要求】如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。
【思路】

判断链表是否有环，如果有环，返回第一个入环的节点。
- 方法一：遍历链表，将每个节点加入到map里，如果发现有一个节点再加入map前就已经存在于map中，说明有环，该节点即为入环节点；如果最后走到null了，说明无环。
- 方法二：两个指针，一快一慢，即一个走一步，一个走两步。如果无环，那么快指针一定会走到结尾；如果有环，那么快指针和慢指针一定会在环里相遇，相遇后，快指针回到head节点，然后快指针和慢指针都变为每次走一步，同时开始走，一定会在入环节点相遇（数学结论）。
二者相交分为三种情况
- 情况一：两个单链表都无环。首先获取两个链表的长度，求得差值；用两个指针，长度长的链表指针先走差值的步数，然后再同时走；如果last1=last2说明它们一定相交，否则不相交。
- 情况二：一个链表有环，一个链表无环，绝对不可能相交。因为一个节点只能有一个next。
- 情况三：两个链表都有环。
  - 两个链表在环出现之前就相交了，之后一直相交。loop1=loop2，即两个链表的入环节点相同，则相交。用两个指针，长度长的链表指针先走差值的步数，然后再同时走；如果两个链表的入环节点都不为空且相等，则相交。
  - 两个链表只共享环。loop1在环中走的时候遇到了loop2，但不相等。

【题目】分别实现反转单向链表和反转双向链表的函数。
【要求】如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)。
【思路】可以用栈或者原地反转。