链表问题总结 (下)
【声明】
欢迎转载，但请保留文章原始出处→_→
文章来源：http://www.jianshu.com/p/08d085b34b2c
联系方式：zmhg871@gmail.com
【正文】
链表是非常基础和灵活的数据结构，在面试中出现的频率非常高。以下是我在学习《剑指offer》过程中对链表问题的总结，希望对大家复习有帮助。
（Java实现）
【目录】
09、判断单链表是否存在环
10、链表中环的节点长度
11、链表中环的入口结点
12、两个链表的第一个公共节点
13、删除链表中重复的结点
14、圆圈中最后剩下的数字
【待整理】
剑指offer，题26：复杂链表的复制
- 09、判断单链表是否存在环
题目描述：输入一个单向链表，判断链表是否有环？
解题思路：
如果一个链表有环，那么用一个指针去遍历，是永远走不到头的。
因此，定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表中存在环；如果走的快的指针走到了链表的末尾都没有追上第一个指针，那么链表中不存在环。
(指针p1,p2，相对位移为1，可以理解为一个静止，另一个每次移动1步，所以有环的情况下必然相遇)
public static boolean hasCircle(ListNode head){
if(head == null)
return false;
ListNode p1 = head;//快指针
ListNode p2 = head;//慢指针
//循环结束标志判断
while(p1 != null && p1.next !=null){
p1 = p1.next.next;
p2 = p2.next;
//一旦两个指针相遇，说明链表是有环的
if(p1 == p2) return true;
}
return false;
}
- 10 链表中环的节点长度
题目描述：一个链表中包含环，求出环中节点的数目？
解题思路：在判断一个链表中是否有环的时候，用到了一快一慢两个指针。如果两个指针相遇，表明链表中有环，两个指针相遇的节点一定在环中。
可以从这个节点继续出发，一边继续向前移动一边计数，当再次回到这个节点的时候，就得到了环中节点的数目了。
public static int getCycleLength(ListNode head){
if(head == null)
return 0;
ListNode p1 = head;//快指针
ListNode p2 = head;//慢指针
//循环结束标志判断
while(p1 != null && p1.next !=null){
p1 = p1.next.next;
p2 = p2.next;
//一旦两个指针相遇，说明链表是有环的
if(p1 == p2) {
p2 = p2.next;
int size = 1;
while(p2 != p1){
p2 = p2.next;
size++;
}
return size;
}
}
return 0;
}
- 11 链表中环的入口结点
题目描述：一个链表中包含环，如何找出环的入口节点？
解题思路：在前面问题的基础上，先定义两个指针 P1 和 P2 指向链表的头结点。如果链表中环有 n 个结点，指针 P1 在链表上向前移动 n 步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。
public static ListNode getCycleStart(ListNode head){
if(head == null) return null;
int n = getCycleLength(head); //获取环中节点数目
if(n ==0) return null; //无环
ListNode p1 = head ;
ListNode p2 = head;
//环的节点数目为n , p1先走n步。
for(int i=0;i<n;i++){
p1 = p1.next;
}
//p1和p2以相同速率前进,直到相遇，找到环的入口
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
- ****12 两个链表的第一个公共节点****
题目描述：输入两个链表，找出它们的第一个公共节点。（剑指offer，题37）
解题思路：
第一种：直接法
在第一个链表上顺序遍历每个结点，每遍历到一个结点的时候，在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和第一个链表上的结点一样，说明两个链表在这个结点上重合，于是就找到了它们的公共结点。如果第一个链表的长度为 m，第二个链表的长度为 n，显然该方法的时间复杂度是 O(mn）。
第二种：使用栈
根据单链表的特点，从公共节点开始，之后所有的节点都是重合的，不可能再出现分叉。所以两个有公共节点而部分重合的链表，拓扑形状看起像一个Y，而不可能像一个X。
经过分析我们发现，如果两个链表有公共结点，那么公共结点出现在两个链表的尾部。如果我们从两个链衰的尾部开始往前比较，最后一个相同的结点就是我们要找的结点。使用栈的特点解决问题：分别将两个链表的节点放入两个栈里，这样两个链尾节点就位于两个栈的栈顶，接下来比较两个栈顶的节点是否相同。如果相同，则把栈顶弹出接着比较下一个栈顶，直到找到最后一个相同的节点。
在上述思路中，我们需要用两个辅助栈。如果链表的长度分别为 m 和 n，那么空间复杂度是 O(n）。这种思路的时间复杂度也是 O(n）。和最开始的蛮力法相比，时间效率得到了提高，相当于是用空间消耗换取了时间效率。
public static void main(String[] args) {
ListNode head1 = new ListNode();
head1.value = 1;
ListNode head2 = new ListNode();
head2.value = 2;
ListNode head3 = new ListNode();
head3.value = 3;
ListNode head4 = new ListNode();
head4.value = 4;
ListNode head5 = new ListNode();
head5.value = 5;
head1.next = head2;
head2.next = head3;
head3.next = head4;
head5.next = head3;
System.out.print(getFirstCommonNode(head1,head5).value);
}
public static ListNode getFirstCommonNode(ListNode head1,ListNode head2){
if(head1 == null || head2 == null) return null;
if(head1 == head2) return head1; //两个链表重合
ListNode tmp1 = head1;
ListNode tmp2 = head2;
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
//入栈
while(tmp1!=null){
stack1.push(tmp1);
tmp1 = tmp1.next;
}
while(tmp2!=null){
stack2.push(tmp2);
tmp2 = tmp2.next;
}
//出栈比较
while(!stack1.empty() && !stack2.empty()){
tmp1 = stack1.pop();
tmp2 = stack2.pop();
if(tmp1 != tmp2)
return tmp1.next;
}
// 有一方先出栈
if (stack1.empty()) {
return temp1;
} else {
return temp2;
}
}
//输出结果：3
第三种：使用快慢指针从头结点开始查找公共节点
我们在上面的方法2中，之所以用到栈，是因为我们想同时遍历到达两个链表的尾结点。其实为解决这个问题我们还有一个更简单的办法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个交点。
在图中的两个链表中，我们可以先遍历一次得到它们的长度分别为 5 和 4， 也就是较长的链表与较短的链表相比多一个结点。第二次先在长的链表上走 1 步，到达结点 2。接下来分别从结点 2 和结点 4 出发同时遍历两个结点， 直到找到它们第一个相同的结点 6，这就是我们想要的结果。
第三种思路和第二种思路相比，时间复杂度都是 O(n)， 但我们不再需要辅助的拢，因此提高了空间效率。 run in O(n) time and use only O(1) memory.
public static ListNode getFirstCommonNode(ListNode head1,ListNode head2){
if(head1 == null || head2 == null) return null;
if(head1 == head2) return head1;
int size1 = getListLength(head1);
int size2 = getListLength(head2);
ListNode tmp1 = head1;
ListNode tmp2 = head2;
//对齐两个链表
if(size1 > size2)
{
for(int i =0;i<(size1 - size2);i++){
tmp1 = tmp1.next;
}
}
else
{
for(int i =0;i<(size2 - size1);i++){
tmp2 = tmp2.next;
}
}
//同时遍历
while(tmp1 != null){
if(tmp1 == tmp2)
return tmp1;
tmp1 = tmp1.next;
tmp2 = tmp2.next;
}
return null;
}
//获取链表长度
public static int getListLength(ListNode head){
if(head == null)
return 0;
ListNode tmp = head;
int size = 0;
while(tmp != null){
size++;
tmp = tmp.next;
}
return size;
}
- 13 删除链表中重复的结点
题目描述：在一个排序的链表中，如何删除重复的结点？ （剑指offer，题57）
例如:
（删除前）1-2-3-3-4-4-5
（删除后）1-2-5
解题思路：
解决这个问题的第一步是确定删除的参数。当然这个函数需要输入待删除链表的头结点。头结点可能与后面的结点重复，也就是说头结点也可能被删除，所以在链表头添加一个结点。
接下来我们从头遍历整个链表。如果当前结点的值与下一个结点的值相同，那么它们就是重复的结点，都可以被删除。为了保证删除之后的链表仍然是相连的而没有中间断开，我们要把当前的前一个结点和后面值比当前结点的值要大的结点相连。我们要确保prev要始终与下一个没有重复的结点连接在一起。
private static ListNode deleteDuplication(ListNode head) {
// 为null
if (head == null) {
return null;
}
// 临时的头结点
ListNode root = new ListNode();
root.next = head;
// 记录前驱结点
ListNode prev = root;
// 记录当前处理的结点
ListNode node = head;
while (node != null && node.next != null) {
// 有重复结点，与node值相同的结点都要删除
if (node.value == node.next.value) {
// 找到下一个不同值的节点，注意其有可能也是重复节点
while (node.next != null && node.next.value == node.value) {
node = node.next;
}
// 指向下一个节点，prev.next也可能是重复结点
// 所以prev不要移动到下一个结点
prev.next = node.next;
}
// 相邻两个值不同，说明node不可删除，要保留
else {
prev.next = node;
prev = prev.next;
}
node = node.next;
}
return root.next;
}
- 14 圆圈中最后剩下的数字
题目描述：0, 1, … , n-1 这 n 个数字排成一个圈圈，从数字 0 开始每次从圆圏里删除第 m 个数字。求出这个圈圈里剩下的最后一个数字。
（约瑟夫环问题 ）（ 剑指offer，题45）
解题思路：
第一种：经典的解法， 用环形链表模拟圆圈。
创建一个总共有 n 个结点的环形链表，然后每次在这个链表中删除第 m 个结点。
public static int lastRemaining(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
List<Integer> list = new LinkedList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
// 要删除元素的位置
int idx = 0;
while (list.size() > 1) {
// 只要移动m-1次就可以移动到下一个要删除的元素上
for (int i = 1; i < m; i++) {
idx = (idx + 1) % list.size();
}
list.remove(idx);
}
return list.get(0);
}
第二种：（待整理）
[2015-09-10]
