常见链表面试题解题思路

1 找中点

快慢指针

1. 奇数中点，偶数上中点
2. 奇数中点，偶数下中点
3. 奇数中点前一个，偶数上中点前一个
4. 奇数中点前一个，偶数下中点前一个

2 回文

1. 遍历压栈法
2. 右半部分压栈法
3. 右半部分改指针法

3 左大中等右小

1. 放入数组，partition
2. 链表法
   

4 特殊链表复制

// 提供特殊的节点
class Node {
    int value;
    Node next; // 指向下一个节点，是无环的
    Node rand; // 随便指向一个节点 ，可能有环
    
    Node(int data) {
		this.value = data;
	}
}

1. map

   1. key 是 Node，Value 是 Node*

   2. map.get(Node).next == map.get(Node.next)

   3. map.get(Node).rand == map.get(Node.rand)

2. 构建映射关系

   1. node1.next = node*，node1*.next = node2 … （原来两个node节点中插入一个复制节点）
   2. 当 node1.rand 指向不为空时，node1*.rand = node1.rand.next
   3. 将复制节点分离

5 俩链表相交问题

三种情况

1. 两个无环相交

2. 一个无环一个有环，不可能相交

3. 两个有环相交

5.1 找到入环节点

单链表入环不可能出来

如图1：快指针走两步，慢指针走一步，总会快慢指针相遇

如图2：相遇后，快指针回到头结点，改为一次走一步，第二次相遇时的节点即为头结点

5.2 俩无环链表相交节点

1. 俩链表最后的节点是同一个节点
   1. node1 和 node2 一直next，直到节点下一个节点为null时停止
   2. 俩节点指向不同地址说明一定没相交
2. 长链表走一个差值的 next 次数
3. 长短链表同时next，直到俩节点相等时，说明是第一个相交节点

5.3 俩有环链表相交节点

1. 入环节点相同，在入环处相交：loop1 == loop2，改无环代码，遇到 loop 停
2. 入环节点不同，在入环前相交：loop1 != loop2，改俩无环链表相交代码