算法初级-03-时间复杂度
2019-07-12 本文已影响0人
囧么肥事
年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容，转移简书）
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：用数组结构实现大小固定的队列和栈
实例2：实现一个特殊的栈，在实现栈的基本功能的基础上，实现返回栈中最小元素的操作
实例3：如何仅用队列结构实现栈结构？如何仅用栈结构实现队列结构？
实例4：猫狗队列
实例5：转圈打印矩阵
实例6：旋转正方形矩阵
实例7：反转单向和双向链表
实例8：“之”字形打印矩阵
实例9：在行列都排好序的矩阵中找数
实例10：打印两个有序链表的公共部分
实例11：判断一个链表是否为回文结构
实例12：将单向链表按某值划分成左边小、中间相等、右边大的形式
实例13：复制含有随机指针节点的链表
实例14：两个单链表相交的一系列问题
实例1
用数组结构实现大小固定的队列和栈
/**
* @description: 用数组结构实现大小固定的队列和栈
*
* 1、数组实现栈
* 使用一个size指针，
* 添加元素
* 当size != arr.length 时可以向栈添加元素 size++
* 当size == arr.lentth 时抛出数组越界异常
* 弹出元素
* 当size != arr.length 时可以从栈顶弹出元素，size - 1
* 当size == arr.lentth 时抛出数组越界异常
*
*
* 2、数组实现队列（这个难度要比实现栈高）
* 使用三个指针
* size
* start -- 表示弹出的元素在队列中所处的位置
* end -- 表示新增的元素应该在队列中所处的位置
*
* @version: 1.0
*/
public class Code_11_ArrayToStackAndQueue {
/**
* 数组结构实现大小固定的栈
*/
public static class ArrayStack {
private Integer[] arr;
private Integer size;
public ArrayStack(int initSize) {
if (initSize < 0)
throw new IllegalArgumentException("The init size is less than 0");
arr = new Integer[initSize];
size = 0;
}
// 弹出栈顶元素值，但是不删除栈顶元素
public Integer peek() {
if (size == 0) return null;
return arr[size - 1];
}
public void push(int obj) {
if (size == arr.length)
throw new ArrayIndexOutOfBoundsException("the stack is full");
arr[size++] = obj;
}
// 弹出栈顶元素并删除栈顶元素，这里只是将下标前移
public Integer pop() {
if (size == 0)
throw new ArrayIndexOutOfBoundsException("The stack is empty");
return arr[--size];
}
}
// 使用数组结构实现一个队列
public static class ArrayQueue {
private Integer[] arr;
private Integer size;
private Integer start; // 拿取一个数，拿取的是哪个位置上的数
private Integer end; // 代表每次新增数应该存放的位置
public ArrayQueue(int initSize) {
if (initSize < 0)
throw new IllegalArgumentException("The init size is less than 0");
arr = new Integer[initSize];
size = 0;
start = 0;
end = 0;
}
public void push(int obj) {
// 是否满
if (size == arr.length)
throw new ArrayIndexOutOfBoundsException("The queue is full");
size++;
arr[end] = obj;
end = end == arr.length - 1 ? 0 : end + 1;
}
public Integer poll() {
if (size == 0)
throw new ArrayIndexOutOfBoundsException("The queue is empty");
size--;
int tmp = start;
start = start == arr.length ? 0 : start + 1;
return arr[tmp];
}
public Integer peek() {
if (size == 0) throw new ArrayIndexOutOfBoundsException("The queue is empty");
return arr[start];
}
}
}
实例2
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返 回栈中最小元素的操作。
【要求】
1．pop、push、getMin操作的时间复杂度都是O(1)。
2．设计的栈类型可以使用现成的栈结构。
import org.omg.CORBA.INTERNAL;
import java.util.Stack;
/**
* @description:
* 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返 回栈中最小元素的操作。
* 【要求】
* 1．pop、push、getMin操作的时间复杂度都是O(1)。
* 2．设计的栈类型可以使用现成的栈结构。
* @version: 1.0
*/
public class Code_12_GetMinStack {
/**
* 准备两个栈
* 一个栈用来存依次进行的数据
* 一个栈用来存最小值
*
* 两个栈存数据都是同步的
*/
public static class MinStack{
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
public MinStack(){
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val){
// 最小值栈如果是空栈，直接入栈
if (minStack.isEmpty()){
minStack.add(val);
} else if (minStack.peek() <= val){
minStack.add(minStack.peek());
} else {
minStack.add(val);
}
dataStack.add(val);
}
public Integer pop(){
if (dataStack.isEmpty()) throw new RuntimeException("Your stack is empty.");
minStack.pop();
return dataStack.pop();
}
public Integer peek(){
if (dataStack.isEmpty()) throw new RuntimeException("Your stack is empty.");
return dataStack.peek();
}
public Integer getMinNum(){
if (dataStack.isEmpty()) throw new RuntimeException("Your stack is empty.");
return minStack.peek();
}
}
/**
* 第二种方式
*
* 也是准备两个栈
* 和第一个不同的是，minStack 只有在出现比当前栈顶小的数的时候才向minStack 中添加数据
* 也就是两个栈添加和弹出元素不是同步的，
* getMin 每次使用 peek 方法返回栈顶
*/
public static class MinStack2 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MinStack2() {
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum <= this.getmin()) {
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
// 弹出dataStack中的栈顶元素时，更新minStack的状态
// 如果弹出的元素和minStack的栈顶元素一样则证明是最小值，此时需要同步弹出minStack栈顶元素
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
int value = this.stackData.pop();
if (value == this.getmin()) {
this.stackMin.pop();
}
return value;
}
public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(3);
System.out.println(minStack.getMinNum());
minStack.push(4);
System.out.println(minStack.getMinNum());
minStack.push(1);
System.out.println(minStack.getMinNum());
System.out.println(minStack.pop());
System.out.println(minStack.getMinNum());
}
}
实例3
如何仅用队列结构实现栈结构？
如何仅用栈结构实现队列结构？
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* @description: 如何仅用队列结构实现栈结构？
* 两个队列实现栈
* <p>
* 如何仅用栈结构实现队列结构？
* 两个栈实现队列
* @version: 1.0
*/
public class Code_13_StackAndQueueConvert {
// 两个栈实现队列
// 1、必须满足每次transfer数据时pop队列必须是空
// 2、必须满足每次都transfer完所有数据
public static class TowStackToQueue {
private Stack<Integer> pushStack; // 专用添加
private Stack<Integer> popStack; // 专用弹出
public TowStackToQueue() {
this.pushStack = new Stack<>();
this.popStack = new Stack<>();
}
public void push(int val) {
pushStack.add(val);
}
public Integer poll() {
if (pushStack.empty() && popStack.empty()) throw new RuntimeException("the queue is empty");
transfer();
return popStack.pop();
}
public Integer peek() {
if (pushStack.empty() && popStack.empty()) throw new RuntimeException("the queue is empty");
transfer();
return popStack.peek();
}
public void transfer(){
// 如果popStack 不为空，不能导数据
if (!popStack.isEmpty()){
return;
}
while (!pushStack.isEmpty()){
popStack.add(pushStack.pop());
}
}
}
// 两个队列实现栈结构
public static class TwoQueuesStack {
private Queue<Integer> dataQueue;
private Queue<Integer> helpQueue;
public TwoQueuesStack() {
dataQueue = new LinkedList<>();
helpQueue = new LinkedList<>();
}
public void push(int val) {
dataQueue.add(val);
}
public Integer peek() {
if (dataQueue.isEmpty())
throw new RuntimeException("Stack is empty!");
while (!dataQueue.isEmpty()){
helpQueue.add(dataQueue.poll());
}
Integer res = helpQueue.peek();
swap(dataQueue, helpQueue);
return res;
}
public Integer pop(){
if (dataQueue.isEmpty())
throw new RuntimeException("Stack is empty!");
while (dataQueue.size() > 1){ // 只剩一个数停止
helpQueue.add(dataQueue.poll());
}
Integer res = dataQueue.poll();
swap(dataQueue, helpQueue);
return res;
}
private void swap(Queue<Integer> a, Queue<Integer> b) {
Queue<Integer> tmp = a;
a = b;
b = tmp;
}
}
}
实例4
猫狗队列 【题目】 宠物、狗和猫的类如下：
public static class Pet {
private String type;
public Pet(String type) {
this.type = type;
}
public String getPetType() {
return this.type;
}
}
public static class Dog extends Pet {
public Dog() {
super("dog");
}
}
public static class Cat extends Pet {
public Cat() {
super("cat");
}
}
实现一种狗猫队列的结构，要求如下： 用户可以调用add方法将cat类或dog类的 实例放入队列中； 用户可以调用pollAll方法，将队列中所有的实例按照进队列 的先后顺序依次弹出； 用户可以调用pollDog方法，将队列中dog类的实例按照 进队列的先后顺序依次弹出； 用户可以调用pollCat方法，将队列中cat类的实 例按照进队列的先后顺序依次弹出； 用户可以调用isEmpty方法，检查队列中是 否还有dog或cat的实例； 用户可以调用isDogEmpty方法，检查队列中是否有dog 类的实例； 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。
import java.util.LinkedList;
import java.util.Queue;
/**
* @description: 猫狗队列
*
* 猫狗队列 【题目】 宠物、狗和猫的类如下：
* public class Pet { private String type; public Pet(String type) { this.type = type; }
* public String getPetType() { return this.type; } }
* public class Dog extends Pet { public Dog() { super("dog"); } }
* public class Cat extends Pet { public Cat() { super("cat"); } }
* 实现一种狗猫队列的结构，要求如下： 用户可以调用add方法将cat类或dog类的 实例放入队列中；
* 用户可以调用pollAll方法，将队列中所有的实例按照进队列 的先后顺序依次弹出；
* 用户可以调用pollDog方法，将队列中dog类的实例按照 进队列的先后顺序依次弹出；
* 用户可以调用pollCat方法，将队列中cat类的实 例按照进队列的先后顺序依次弹出；
* 用户可以调用isEmpty方法，检查队列中是 否还有dog或cat的实例；
* 用户可以调用isDogEmpty方法，检查队列中是否有dog 类的实例；
* 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例
*/
public class Code_14_DagCatQueue {
public static class Pet {
private String type;
public Pet(String type) {
this.type = type;
}
public String getPetType() {
return this.type;
}
}
public static class Dog extends Pet {
public Dog() {
super("dog");
}
}
public static class Cat extends Pet {
public Cat() {
super("cat");
}
}
/**
* 实际进入猫狗队列的实体
*/
public static class PetEnter {
private Pet pet;
private long count;
public PetEnter(Pet tytp, long count) {
this.pet = tytp;
this.count = count;
}
public Pet getPet() {
return pet;
}
public long getCount() {
return count;
}
public String getEnterPetType() {
return this.pet.getPetType();
}
}
// 猫狗队列
public static class DogCatQueue {
private Queue<PetEnter> dogQueue;
private Queue<PetEnter> catQueue;
private long count;
public DogCatQueue() {
this.dogQueue = new LinkedList<>();
this.catQueue = new LinkedList<>();
this.count = 0;
}
public void add(Pet pet) {
if (pet.getPetType().equals("dog"))
dogQueue.add(new PetEnter(pet, count++));
else if (pet.getPetType().equals("cat"))
catQueue.add(new PetEnter(pet, count++));
else
throw new RuntimeException("err, not dog or cat");
}
public Pet pollAll() {
if (!dogQueue.isEmpty() && !catQueue.isEmpty()) {
if (this.catQueue.peek().count > this.dogQueue.peek().count) {
return this.dogQueue.poll().getPet();
} else {
return this.catQueue.poll().getPet();
}
} else if (!dogQueue.isEmpty()) {
return this.dogQueue.poll().getPet();
} else if (!catQueue.isEmpty()) {
return this.catQueue.poll().getPet();
} else {
throw new RuntimeException("err, queue is empty!");
}
}
public Dog pollDog() {
if (!this.isDogQueueEmpty()) {
return (Dog) this.dogQueue.poll().getPet();
} else {
throw new RuntimeException("Dog queue is empty!");
}
}
public Cat pollCat() {
if (!this.isCatQueueEmpty()) {
return (Cat) this.catQueue.poll().getPet();
} else
throw new RuntimeException("Cat queue is empty!");
}
public boolean isEmpty() {
return this.dogQueue.isEmpty() && this.catQueue.isEmpty();
}
public boolean isDogQueueEmpty() {
return this.dogQueue.isEmpty();
}
public boolean isCatQueueEmpty() {
return this.catQueue.isEmpty();
}
}
public static void main(String[] args) {
DogCatQueue test = new DogCatQueue();
Pet dog1 = new Dog();
Pet cat1 = new Cat();
Pet dog2 = new Dog();
Pet cat2 = new Cat();
Pet dog3 = new Dog();
Pet cat3 = new Cat();
test.add(dog1);
test.add(cat1);
test.add(dog2);
test.add(cat2);
test.add(dog3);
test.add(cat3);
test.add(dog1);
test.add(cat1);
test.add(dog2);
test.add(cat2);
test.add(dog3);
test.add(cat3);
test.add(dog1);
test.add(cat1);
test.add(dog2);
test.add(cat2);
test.add(dog3);
test.add(cat3);
while (!test.isDogQueueEmpty()) {
System.out.println(test.pollDog().getPetType());
}
while (!test.isEmpty()) {
System.out.println(test.pollAll().getPetType());
}
}
}
实例5
转圈打印矩阵
【题目】 给定一个整型矩阵matrix，请按照转圈的方式打印它。
例如：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
打印结果为：1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10
【要求】 额外空间复杂度为O(1)。
所谓的转圈打印矩阵
5_1_转圈打印矩阵示例.png
宏观思想：按照一圈一圈的去打印，一层一层的处理
5_2_层次处理.png
根据对角线的两个点，左上角和右下角的点（ax,ay）(bx,by)
来推导其他点的变动
/**
* @description: 转圈打印矩阵
*
* 转圈打印矩阵 【题目】 给定一个整型矩阵matrix，请按照转圈的方式打印它。
* 例如：
* 1 2 3 4
* 5 6 7 8
* 9 10 11 12
* 13 14 15 16
* 打印结果为：
* 1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10
*
* 【要求】 额外空间复杂度为O(1)。
* @version: 1.0
*/
public class Code_15_PrintMatrixSpiralOrder {
// 43
public static void printMatrixSpiralOrder(int[][] matrix) {
if (matrix == null || matrix.length < 1) return;
// A(ax,ay) B(bx,by) 对角线的俩个点
int ax = 0;
int ay = 0;
int bx = matrix.length - 1;
int by = matrix[0].length - 1;
// 保证两点是存在的
while (ax <= bx && ay <= by) {
// 每次传入两个对角线
printEdge(matrix, ax++, ay++, bx--, by--);
System.out.println(); // 每打印一圈换行，方便查看结果
}
}
public static void printEdge(int[][] matrix, int ax, int ay, int bx, int by) {
// 两点在一条直线上，不是对角线处理
if (ay == by) {
for (int i = ax; i <= bx; i++) {
System.out.println(matrix[i][ay] + " ");
}
} else if (ax == bx) {
for (int i = by; i >= ay; i--) {
System.out.println(matrix[ax][i] + " ");
}
} else { // 对角线，成圈打印
int curX = ax;
int curY = ay;
// 向右
while (curY != by) {
System.out.print(matrix[ax][curY] + " ");
curY++;
}
// 向下
while (curX != bx) {
System.out.print(matrix[curX][by] + " ");
curX++;
}
// 向左
while (curY != ay) {
System.out.print(matrix[bx][curY] + " ");
curY--;
}
// 向上
while (curX != ax) {
System.out.print(matrix[curX][ay] + " ");
curX--;
}
}
}
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
{ 13, 14, 15, 16 }, {17,18,19,20} };
printMatrixSpiralOrder(matrix);
}
}
实例6
旋转正方形矩阵
【题目】 给定一个整型正方形矩阵matrix，请把该矩阵调整成 顺时针旋转90度的样子。
1 2 3
4 5 6
7 8 9
旋转90°
7 4 1
8 5 2
9 6 3
【要求】 额外空间复杂度为O(1)。
分析：
6_1_矩阵翻转90度坐标点变换.png
/**
* @description: 旋转正方形矩阵, 翻转90度
* @version: 1.0
*/
public class Code_16_RotateMatrix{
public static void rotateMatrix(int[][] matrix){
if (matrix == null || matrix.length == 0) return;
int tR = 0;
int tC = 0;
int dR = matrix.length - 1;
int dC = matrix[0].length - 1;
while (tR < dR) {
rotate(matrix, tR++, tC++, dR--, dC--);
}
}
// 翻转
public static void rotate(int[][] m, int tR, int tC, int dR, int dC){
int times = dR - tR;// 本圈遍历次数
int tmp = 0;
for (int i = 0; i < times; i++) {
tmp = m[tR][tC + i];
m[tR][tC + i] = m[dR - i][tC];
m[dR - i][tC] = m[dR][dC - i];
m[dR][dC - i] = m[tR + i][dC];
m[tR + i][dC] = tmp;
}
}
public static void printMatrix(int[][] matrix) {
for (int i = 0; i != matrix.length; i++) {
for (int j = 0; j != matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
printMatrix(matrix);
rotateMatrix(matrix);
System.out.println("=========");
printMatrix(matrix);
}
}
实例7
反转单向和双向链表
【题目】 分别实现反转单向链表和反转双向链表的函数。
【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间 复杂度要求为O(1)
一、反转单向链表
虽然对于单向链表的写法已经知道了，但是一直对于它处于强行记忆的状态。还好发现了一篇写的非常好的文章，作者真的是用心良苦，这里默默的给他点个赞[图片上传失败...(image-96ff82-1562920150151)]。
原文：https://blog.csdn.net/xyh269/article/details/70238501
现在有一个单向链表如下图所示：
image
反转后如下所示：
image
接下来解析反转函数：
image
第一步：next = head.next
将 head.next 赋值给 next 变量，也就是说 next 指向了节点2，先将节点2 保存起来。
第二步：head.next = pre
将 pre 变量赋值给 head.next，即 节点1 指向了 null
第三步：pre = head
将 head 赋值给了 pre，即 pre 指向节点1，将节点1 设为“上一个节点”
第四步：head = next
将 next 赋值给 head，即 head 指向了节点2。将节点2 设为“头节点”
第一次循环完毕，进入第二次循环，如下图
image
第二次循环完毕，以此类推！第三次第四次第五次循环。最后反转成如下图
image
看完上面别人的图，个人总结：所谓的反转链表其实就是每次断开一个节点，置为头结点，指向之前已经反转好的节点。
/**
* @description: 反转单向和双向链表
* 【题目】 分别实现反转单向链表和反转双向链表的函数。
* 【要求】 如果链表长度为N，
* 时间复杂度要求为O(N)，
* 额外空间 复杂度要求为O(1)
* @version: 1.0
*/
public class Code_17_RotateList_RotateDoubleList {
// 单向链表
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
// 反转单向链表
public static Node reverseList(Node head) {
if (head == null || head.next == null)
return head;
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
// 双向链表
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
public static DoubleNode reverseList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next; // 和单向链表不同的地方，唯一的就是上个指向
pre = head;
head = next;
}
return pre;
}
public static void printLinkedList(Node head) {
System.out.print("Linked List: ");
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
System.out.println();
}
public static void printDoubleLinkedList(DoubleNode head) {
System.out.print("Double Linked List: ");
DoubleNode end = null;
while (head != null) {
System.out.print(head.value + " ");
end = head;
head = head.next;
}
System.out.print("| ");
while (end != null) {
System.out.print(end.value + " ");
end = end.last;
}
System.out.println();
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
printLinkedList(head1);
head1 = reverseList(head1);
printLinkedList(head1);
DoubleNode head2 = new DoubleNode(1);
head2.next = new DoubleNode(2);
head2.next.last = head2;
head2.next.next = new DoubleNode(3);
head2.next.next.last = head2.next;
head2.next.next.next = new DoubleNode(4);
head2.next.next.next.last = head2.next.next;
printDoubleLinkedList(head2);
printDoubleLinkedList(reverseList(head2));
}
}
实例8
“之”字形打印矩阵
【题目】 给定一个矩阵matrix，按照“之”字形的方式打印这 个矩阵，
例如：
1 2 3 4
5 6 7 8
9 10 11 12
“之”字形打印的结果为：
1，2，5，9，6，3，4，7，10，11， 8，12
【要求】 额外空间复杂度为O(1)。
之字形打印走位示例
8_1_之字打印矩阵走位.png
之字打印坐标变换
8_2_之字打印坐标变换.png
如图：A，B两点最初在（0,0）点
A(aR, aC) B(bR, bC)
A点坐标，A一直向右前进，当遇到边界时，改为向下前进
B点坐标，B一直向下前进，当遇到边界时，改为向右前进
/**
* @description:
* “之”字形打印矩阵
* 【题目】 给定一个矩阵matrix，按照“之”字形的方式打印这 个矩阵，
* 例如：
* 1 2 3 4
* 5 6 7 8
* 9 10 11 12
*
* “之”字形打印的结果为：
* 1，2，5，9，6，3，4，7，10，11， 8，12
* 【要求】 额外空间复杂度为O(1)。
*
* @version: 1.0
*/
public class Code_18_ZigZagPrintMatrix {
public static void zigZagPrintMatrix(int[][] matrix) {
// A点坐标，A一直向右前进，当遇到边界时，改为向下前进
int aR = 0;
int aC = 0;
// B点坐标，B一直向下前进，当遇到边界时，改为向右前进
int bR = 0;
int bC = 0;
// 下前进边界，即总行
int enbR = matrix.length - 1;
int enbC = matrix[0].length - 1; // 右前进边界，即总列
// 向哪个方向进行打印标志
boolean fromUp = false;
// 结束打印条件：
// 以A点分析,A点前进路线是 A--> 右 --> 遇边界 --> 下
// 当A--> 下 遇到边界时，就是结束之时
// 同理，以B作为分析一样，
while (aR != enbR + 1) {
printLevel(matrix, aR, aC, bR, bC, fromUp);
aR = aC == enbC ? aR + 1 : aR;
aC = aC == enbC ? aC : aC + 1;
bC = bR == enbR ? bC + 1 : bC;
bR = bR == enbR ? bR : bR + 1;
fromUp = !fromUp;
}
System.out.println();
}
public static void printLevel(int[][] m, int aR, int aC, int bR, int bC, boolean fromUp) {
if (fromUp) {
while (aR != bR + 1)
System.out.print(m[aR++][aC--] + " ");
} else {
while (bC != aC + 1)
System.out.print(m[bR--][bC++] + " ");
}
}
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
zigZagPrintMatrix(matrix);
}
}
实例9
在行列都排好序的矩阵中找数
【题目】 给定一个有N*M的整型矩阵matrix和一个整数K， matrix的每一行和每一 列都是排好序的。
实现一个函数，判断K 是否在matrix中。
例如：
0 1 2 5
2 3 4 7
4 4 4 8
5 7 7 9
如果K为7，返回true；
如果K为6，返 回false。
【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)。
行列都排好序的矩阵中找数_坐标变换
9_1_行列都排好序的矩阵中找数_坐标变换.png
从右上角点(R, C)出发开始遍历查找
终止条件是查找到目标数或者当前点到达了左下角的
最后一个点依然没有找到目标数，停止
当前点小于 K (如图2,图3)
R++
当前点大于 K
C--
当前点等于 k
返回true
/**
* @description: 在行列都排好序的矩阵中找数
*
* 【题目】
* 给定一个有N*M的整型矩阵matrix和一个整数K， matrix的每一行和每一 列都是排好序的。
* 实现一个函数，判断K 是否在matrix中。
* 例如：
* 0 1 2 5
* 2 3 4 7
* 4 4 4 8
* 5 7 7 9
* 如果K为7，返回true；
* 如果K为6，返 回false。
* 【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)。
* @version: 1.0
*/
public class Code_19_FindNumInSortedMatrix {
public static boolean findNumInSoftedMatrix(int[][] matrix, int k){
if (matrix == null || matrix.length == 0) return false;
// 从右上角点出发开始遍历查找 (R, C)
int R = 0;
int C = matrix[0].length - 1;
// 终止条件是查找到目标数或者当前点到达了左下角的最后一个点依然没有找到目标数，停止
while (R < matrix.length && C > -1){
if (matrix[R][C] > k)
C--;
else if (matrix[R][C] < k)
R++;
else
return true;
}
return false;
}
public static void main(String[] args) {
int[][] matrix = new int[][] { { 0, 1, 2, 3, 4, 5, 6 },// 0
{ 10, 12, 13, 15, 16, 17, 18 },// 1
{ 23, 24, 25, 26, 27, 28, 29 },// 2
{ 44, 45, 46, 47, 48, 49, 50 },// 3
{ 65, 66, 67, 68, 69, 70, 71 },// 4
{ 96, 97, 98, 99, 100, 111, 122 },// 5
{ 166, 176, 186, 187, 190, 195, 200 },// 6
{ 233, 243, 321, 341, 356, 370, 380 } // 7
};
int K = 233;
System.out.println(findNumInSoftedMatrix(matrix, K));
}
}
实例10
打印两个有序链表的公共部分
【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
思路：类似外排的方式进行遍历两个链表
/**
* @description: 打印两个有序链表的公共部分
* 【题目】 给定两个有序链表的头指针head1和head2，打印两个 链表的公共部分。
* @version: 1.0
*/
public class Code_20_PrintCommonPart {
public static class List {
public List next;
public int val;
public List(int data) {
this.val = data;
}
}
// 打印两个有序链表公共部分
public static void printTowSortedListCommonPart(List head1, List head2) {
while (head1 != null && head2 != null) {
if (head1.val > head2.val)
head2 = head2.next;
else if (head1.val < head2.val)
head1 = head1.next;
else{
System.out.print(head1.val + " ");
head1 = head1.next;
head2 = head2.next;
}
}
}
public static void printLinkedList(List node) {
System.out.print("Linked List: ");
while (node != null) {
System.out.print(node.val + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
List node1 = new List(2);
node1.next = new List(3);
node1.next.next = new List(5);
node1.next.next.next = new List(6);
List node2 = new List(1);
node2.next = new List(2);
node2.next.next = new List(5);
node2.next.next.next = new List(7);
node2.next.next.next.next = new List(8);
printLinkedList(node1);
printLinkedList(node2);
printTowSortedListCommonPart(node1, node2);
}
}
实例11
判断一个链表是否为回文结构
【题目】 给定一个链表的头节点head，请判断该链表是否为回 文结构。
例如：
1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。
进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。
思路：回文结构，就是镜面反射
第一种思路：遍历链表，将节点存入栈中，需要 n extra space
再次遍历链表，和栈中每次弹出的节点进行比较
第二种思路：快慢指针，遍历链表找到中间节点（奇数链表找到中间的前一个节点），然后将中间节点之后的节点存入栈中，需要 n/2 extra space
再次遍历链表，和栈中每次弹出的节点进行比较，栈中节点比较完，只要没有不同的节点，则回文链表。
第三种思路：O(1) 空间复杂度
1 -> 2 -> 3 -> 2 -> 1
快慢指针找到中间节点
将中间节点之后的链表进行逆序
从两端开始遍历，任意一个到达null时停止，在这个过程中，如果没有不同节点，则回文结构
最后复原原链表结构
import java.util.Stack;
/**
* @description: 判断一个链表是否为回文结构
* 【题目】 给定一个链表的头节点head，请判断该链表是否为回 文结构。
* 例如： 1->2->1，返回true。
* 1->2->2->1，返回true。
* 15->6->15，返回true。
* 1->2->3，返回false。
* 进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。
* @version: 1.0
*/
public class Code_21_IsPalindromeList {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
// need n extra space 需要 O(N) 的空间复杂度
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<>();
Node cur = head;
// 载入栈
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 比较
while (head != null) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
// need n/2 extra space
public static boolean isPalindrome2(Node head) {
if (head == null || head.next == null) return true;
Node n1 = head;
Node n2 = head;
// 双指针遍历找到 mid
// 终止条件：n2 到达终点，即n2 不能满足走下一步（一次跳两个节点）
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
// 存储后半截到Stack
Stack<Node> stack = new Stack<>();
n1 = n1.next;
while (n1 != null) {
stack.push(n1);
n1 = n1.next;
}
// 比较
while (!stack.isEmpty()) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
while (n2.next != null && n2.next.next != null) { // find mid node
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
n2 = n1.next; // n2 -> right part first node
n1.next = null; // mid.next -> null
Node help = null; // 辅助反转链表
while (n2 != null){
help = n2.next;
n2.next = n1;
n1 = n2;
n2 = help;
}
help = n1; // 记录最后一个节点
n2 = head; // n2 指向违反转链表的头结点
boolean res = true;
while (n1 != null && n2 != null){
if (n1.value != n2.value){
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
// 记录中心点位置
n1 = help.next;
// 恢复为原链表结构
help.next = null;
while(n1 != null){
n2 = n1.next;
n1.next = help;
help = n1;
n1 = n2;
}
return res;
/*
Code_17_RotateList_RotateDoubleList
反转链表，核心步骤
Node pre = null;
Node next = null;
while (head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre; // pre 是反转后的链表的头结点
*/
}
// need O(1) extra space
public static void printLinkedList(Node node) {
System.out.print("Linked List: ");
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
}
}
实例12
将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】 给定一个单向链表的头节点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的节点即可。对某部分内部的节点顺序不做 要求。
进阶： 在原问题的要求之上再增加如下两个要求。
在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左 到右的 顺序与原链表中节点的先后次序一致。
例如：链表9->0->4->5->1，pivot=3。
调整后的链表是0->1->9->4->5。
在满足原问题要求的同时，左部分节点从左到 右为0、1。
在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再 讨论；
右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4， 最后出现5。
如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
/**
* @description: 将单向链表按某值划分成左边小、中间相等、右边大的形式
*
* 【题目】 给定一个单向链表的头节点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的节点即可。对某部分内部的节点顺序不做 要求。
* 进阶： 在原问题的要求之上再增加如下两个要求。 在左、中、右三个部分的内部也做顺序要求，
* 要求每部分里的节点从左 到右的 顺序与原链表中节点的先后次序一致。 例如：链表9->0->4->5->1，pivot=3。
* 调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到 右为0、1。
* 在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再 讨论；右部分节点 从左到右为9、4、5。
* 在原链表中也是先出现9，然后出现4， 最后出现5。
*
* 如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
* @version: 1.0
*/
public class Code_22_SmallerEqualBigger {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
// 43 58 09
// 类似荷兰国旗问题，这里使用O（N）的空间复杂度来转换为数组，进行荷兰国旗问题解决，最后回写到原链
public static Node listPartition1(Node head, int pivot) {
if (head == null) {
return head;
}
Node cur = head;
int i = 0;
while (cur != null){
i++;
cur = cur.next;
}
Node[] arr = new Node[i];
cur = head;
i = 0;
// 装载进数组
while (cur != null){
arr[i++] = cur;
cur = cur.next;
}
// 按照荷兰国旗方式进行分区
arrPartition(arr, pivot);
// 回写
for (i = 1; i < arr.length; i++) {
arr[i - 1].next = arr[i];
}
arr[i - 1].next = null;
return arr[0];
}
public static void arrPartition(Node[] arr, int pivot){
int less = -1;
int more = arr.length;
int cur = 0;
while (cur != more){
if (arr[cur].value < pivot){
swap(arr, ++less ,cur++);
} else if (arr[cur].value > pivot){
swap(arr, --more, cur);
} else {
cur++;
}
}
}
public static void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
public static Node listPartition2(Node head, int pivot) {
Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node bH = null; // big head
Node bT = null; // big tail
Node next = null; // save next node
// 每次从链表中弹出首节点，存放到这三个区域链表中
while (head != null) {
next = head.next;
head.next = null; // 弹出首节点
if (head.value > pivot){
if (bH == null){
bH = head;
bT = head;
} else {
bT.next = head;
bT = head; // 尾节点指向新节点
}
} else if (head.value < pivot){
if (sH == null){
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
} else {
if (eH == null){
eH = head;
eT = head;
} else {
eT.next = head;
eT = head;
}
}
head = next;
}
// small and equal reconnect
// 合并小区域和等区域
if(sT != null) {
sT.next = eH;
eT = eT == null ? sT : eT;
}
// 合并等于区域和大区域
if (eT != null) {
eT.next = bH;
}
// 小区域不为空 ？（返回小区域+等于区域+大区域链总链） ： （返回等于区域+大区域链）
// 等于区域不为空 ？（返回等于区域+大区域链总链）：（大于区域链）
return sH != null ? (sH) :(eH != null ? eH : bH);
}
public static void printLinkedList(Node node) {
System.out.print("Linked List: ");
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head1 = new Node(7);
head1.next = new Node(9);
head1.next.next = new Node(1);
head1.next.next.next = new Node(8);
head1.next.next.next.next = new Node(5);
head1.next.next.next.next.next = new Node(2);
head1.next.next.next.next.next.next = new Node(5);
printLinkedList(head1);
head1 = listPartition1(head1, 5);
// head1 = listPartition2(head1, 5);
printLinkedList(head1);
}
}
实例13
复制含有随机指针节点的链表
【题目】 一种特殊的链表节点类描述如下：
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) 内完成原问题要实现的函数。
思路：
1、忽略random指针，复制并链接每一个节点成一个新链
2、遍历新链表，每次取出两个节点。
根据原节点，查找新节点对应的random指针指向的节点（如图2）
3、拆分链表
将组合链表拆分为复制链表和原链表
13_1_复制含有随机指针节点的链表.png
import java.util.HashMap;
/**
* @description: 复制含有随机指针节点的链表
* 【题目】 一种特殊的链表节点类描述如下：
* 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) 内完成原问题要实现的函数。
* @version: 1.0
*/
public class Code_23_CopyListWithRandom {
public static class Node {
public int value;
public Node next;
public Node rand; // 随机指针
public Node(int data) {
this.value = data;
}
}
// need n extra space
public static Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.value)); // copy the cur node
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
public static Node copyListWithRand2(Node head) {
if (head == null) return head;
Node cur = head;
Node next = null; // 每次都是指向下一次循环的头结点，即保存下一次循环的头结点位置
// 复制每个节点，并连接成为一个新链
while (cur != null) {
next = cur.next; // 保留下一个头结点位置
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next; // 重置遍历的头结点
}
// 拷贝random 节点
Node curCopy = null;
cur = head;
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand == null ? null : cur.rand.next;
cur = next;
}
// 分开copy 链和原链
Node res = head.next;
cur = head;
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next == null ? null : next.next;
cur = next;
}
return res;
}
public static void printRandLinkedList(Node head) {
Node cur = head;
System.out.print("order: ");
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
cur = head;
System.out.print("rand: ");
while (cur != null) {
System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
cur = cur.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
Node res1 = null;
Node res2 = null;
printRandLinkedList(head);
res1 = copyListWithRand1(head);
printRandLinkedList(res1);
res2 = copyListWithRand2(head);
printRandLinkedList(res2);
printRandLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(6);
head.rand = head.next.next.next.next.next; // 1 -> 6
head.next.rand = head.next.next.next.next.next; // 2 -> 6
head.next.next.rand = head.next.next.next.next; // 3 -> 5
head.next.next.next.rand = head.next.next; // 4 -> 3
head.next.next.next.next.rand = null; // 5 -> null
head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4
printRandLinkedList(head);
res1 = copyListWithRand1(head);
printRandLinkedList(res1);
res2 = copyListWithRand2(head);
printRandLinkedList(res2);
printRandLinkedList(head);
System.out.println("=========================");
}
}
实例14
两个单链表相交的一系列问题
【题目】 在本题中，单链表可能有环，也可能无环。
给定两个 单链表的头节点 head1和head2，这两个链表可能相交，也可能 不相交。
请实现一个函数， 如果两个链表相交，请返回相交的 第一个节点；
如果不相交，返回null 即可。
要求：如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外 空间复杂度请达到O(1)。
思路
这道题可以拆分为几道题
1、单链表是否有环
2、两个无环单链表是否相交
3、两个有环单链表是否相交
这里先说说不考虑空间复杂度做法
最快做法，需要额外的空间，使用哈希表 HashSet<Node>
1、判断单链表是否有环
将链表head节点循环存入 哈希表，哈希表返回false，成环
通过哈希表来进行快速查找到环节点
HashSet<Node> set
HashSet集合特点：不能存储 Key 相同的值，
即存入值时返回false，则证明set里面已经存在了这个节点
遍历链表，依次将链表的节点存放到HashSet
遇到HashSet返回false时，记录这个节点，此节点就是环节点，并返回
set ---> 1 --->true
set ---> 2 --->true
set ---> 3 --->true
set ---> 4 --->true
set ---> 5 --->true
set ---> 2 --->false --> 返回此节点
2、判断两个无环单链表是否相交
同理1
通过HashSet查找两个无环链表交点
先遍历head1，将节点一次存入set
在遍历head2，遇到存set时返回false则证明存在交叉点，返回此交叉点
，head2 遍历到结束依然没有返回false则证明不存在交叉点，返回null
PS：注意：这里说的同一个节点，跟节点的value值没有任何关系，HashSet判断是否是同一个节点，比较的是内存地址。
哈希表查找是否有环
14_img_01_哈希表_01_单链表是否有环.png
哈希表查找两个无环链表交点
14_img_01_哈希表_02_两个无环单链表是否有交点.png
当然，根据题目要求，这里空间复杂度要求为O(1), 显然不能使用上述做法
1、单链表是否有环
通过快慢指针查找环节点
Node f 快节点：一次跳两个节点
Node s 慢节点：一次跳一个节点
快慢节点初始都指向 首节点（如图1）
循环遍历，当快慢节点第一次相交时（如图5），
快节点重新指向首节点，慢节点保持不变（如图6）
继续遍历，当快慢节点再一次相交时（如图7）
返回此节点
快慢指针查找环节点
14_img_11_快慢指针_01_单链表是否有环.png
2、判断两个无环单链表是否相交
不采用哈希表两个无环单链表查找交点
采用两个变量分别记录
count 记录链表的长度
tail 记录尾节点位置
先遍历head1 记录count1 和tail1
再遍历head2 记录count2 和tail2
比较 if(tail1 != tail2) return null
因为是单链表，若有交点，则尾节点一定相同。
比较两个链表长度
这里假设 head1 比 head2 长
count = count1 - count2
让head1 比head2 多走count 步（如图1），然后head1和head2同时进行遍历
当两个链表相交时返回交点（如图2）
当两个链表遍历完都无交点则返回null
两个无环单链表是否相交
14_img_12_快慢指针_01_两个无环单链表是否有交点.png
接下来考虑两个有环单链表相交问题
PS：注意，一个有环，一个无环，不存在交点，因为是单链表。
14_img_13_快慢指针_01_两个有环单链表相交有三种拓扑结构.png
两个有环链表查找交叉点
两个有环链表有三种拓扑结构：各自成环（无交点），相交于环外，相交于环内
各自成环、相交于环外、内判断方式：根据前面返回的交点（loop1、loop2）判断
if(loop1 == loop2) 环外
if(loop1 != loop2) 环内 或者 各自成环
loop1继续遍历，遍历完毕没有找到loop2，则是各自成环。
loop1继续遍历，遍历找到loop2点，则是环内
返回loop1，loop2都可以作为第一个相交的节点
相交于环外
处理方式：按照两个无环单链表相交节点的查找方式进行查找
处理范围：head1~loop1 head2~loop2 （如图3）
14_img_14_快慢指针_01_两个无环单链表相交有三种拓扑结构.png
/**
* @description: 两个单链表相交的一系列问题
* 【题目】 在本题中，单链表可能有环，也可能无环。
* 给定两个 单链表的头节点 head1和head2，这两个链表可能相交，也可能 不相交。
* 请实现一个函数， 如果两个链表相交，请返回相交的 第一个节点；
* 如果不相交，返回null 即可。 要
*
* 求：如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外 空间复杂度请达到O(1)
*
* 这道题可以拆分为几道题
*
* 1、单链表是否有环
* 2、两个无环单链表是否相交
* 3、两个有环单链表是否相交
*
* 最快做法，需要额外的空间，使用哈希表 HashSet<Node>
*
* 1、判断单链表是否有环
* 将链表head节点循环存入 哈希表，哈希表返回false，成环
*
* 2、判断两个无环单链表是否相交
* 同理 1
*/
public class Code_24_FindFirstIntersectNode {
public static class Node{
public int value;
public Node next;
public Node(int data){
this.value = data;
}
}
private static Node getIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null){
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
System.out.println("loop1: " + loop1);
System.out.println("loop2: " + loop2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null){
return bothLoop(head1, loop1, head2, loop2);
}
// 不存在一个有环一个无环结构相交
return null;
}
/**
* 双指针判断链表是否有环，并返回第一个环节点
* @return 第一个环节点
*/
public static Node getLoopNode(Node head){
if(head == null && head.next == null && head.next.next == null) // 最少三个节点成环
return null;
Node s = head.next;
Node f = head.next.next;
while (s != f) { // s等于f时两指针第一次相交，返回
if (f.next == null || f.next.next == null)
return null;// 快指针到达了尾节点null，证明不成环
s = s.next;
f = f.next.next;
}
f = head; // 快指针从头开始遍历，此时跨步和慢指针一样
while (f != s){
f = f.next;
s = s.next;
}
return s; // or f
}
/**
* 判断两个无环单链表是否相交
* @return 第一次相交节点 或者 null
*/
public static Node noLoop(Node head1, Node head2){
if (head1 == null || head2 == null)
return null; // 任意一个单链表null，不存在交点
Node cur1 = head1;
Node cur2 = head2;
int count = 0; // 记录单链表长度
// 遍历单链表head1，记录链表长度，和尾节点
while (cur1 != null){
count++;
cur1 = cur1.next;
}
while (cur2 != null){
count--;
cur2 = cur2.next;
}
if (cur1 != cur2) return null;// 如果两个单链表的尾节点不同，一定不相交
cur1 = count >= 0 ? head1 : head2; // cur1 指向 big one
cur2 = cur1 == head1 ? head2 : head1; // cur2 指向 small one
count = Math.abs(count); // 绝对值
while (count != 0){ // 让长链先走 count 步
cur1 = cur1.next;
count--;
}
while (cur1 != cur2){ // 相交停止
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1; // or cur2
}
//36
/**
* 两个有环单链表是否相交
* @param head1
* @param loop1 第一个链表环节点
* @param head2
* @param loop2 第二个链表环节点
* @return 第一个相交节点
*
* 两个有环链表有三种拓扑结构：各自成环不相交，环外相交，环内相交
*
* loop1 == loop2 true，环外相交
* false，循环遍历head1 ，从loop1 开始遍历，到再一次经过loop1，
* 若找到loop2 节点，相交 返回loop1 或者 loop2 ----> 环内
* 若没找到loop2， 不相交 各自成环
*/
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
if (loop1 == loop2) { // 环外
Node cur1 = head1;
Node cur2 = head2;
int count = 0;
while (cur1 != loop1){
count++;
cur1 = cur1.next;
}
while (cur2 != loop2){
count--;
cur2 = cur2.next;
}
cur1 = count >= 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
count = Math.abs(count);
while (count != 0) {
cur1 = cur1.next;
count--;
}
while (cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else { // 各自成环不相交或者环内相交
Node cur = loop1.next;
while (cur != loop1){
if (cur == loop2)
return loop2;
cur = cur.next;
}
}
return null;
}
public static void main(String[] args) {
// 1->2->3->4->5->6->7->null
Node head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
head1.next.next.next = new Node(4);
head1.next.next.next.next = new Node(5);
head1.next.next.next.next.next = new Node(6);
head1.next.next.next.next.next.next = new Node(7);
// 0->9->8->6->7->null
Node head2 = new Node(0);
head2.next = new Node(9);
head2.next.next = new Node(8);
head2.next.next.next = head1.next.next.next.next.next; // 8->6
System.out.println("两个无环单链表：" + getIntersectNode(head1, head2).value);
// 1->2->3->4->5->6->7->4...
head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
head1.next.next.next = new Node(4);
head1.next.next.next.next = new Node(5);
head1.next.next.next.next.next = new Node(6);
head1.next.next.next.next.next.next = new Node(7);
head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
// 0->9->8->2...
head2 = new Node(0);
head2.next = new Node(9);
head2.next.next = new Node(8);
head2.next.next.next = head1.next; // 8->2
System.out.println("两个有环单链表，且是环外结构：" + getIntersectNode(head1, head2).value);
// 0->9->8->6->4->5->6..
head2 = new Node(0);
head2.next = new Node(9);
head2.next.next = new Node(8);
head2.next.next.next = head1.next.next.next.next.next; // 8->6
System.out.println("两个有环单链表，且是环内结构：" + getIntersectNode(head1, head2).value);
}
}
注：以上皆是学习算法课程总结
