年輕即出發(fā)...
簡書：http://www.reibang.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源碼：https://github.com/zqtao2332
個(gè)人網(wǎng)站：http://www.zqtaotao.cn/ （停止維護(hù)更新內(nèi)容，轉(zhuǎn)移簡書）
? 咆哮怪獸一枚...嗷嗷嗷...趁你現(xiàn)在還有時(shí)間萌焰，盡你自己最大的努力鸳碧。努力做成你最想做的那件事猎唁，成為你最想成為的那種人姿现，過著你最想過的那種生活油狂。也許我們始終都只是一個(gè)小人物健霹，但這并不妨礙我們選擇用什么樣的方式活下去买置，這個(gè)世界永遠(yuǎn)比你想的要更精彩速警。
最后：喜歡編程叹誉，對生活充滿激情
本節(jié)內(nèi)容預(yù)告
實(shí)例1：用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)大小固定的隊(duì)列和棧
實(shí)例2：實(shí)現(xiàn)一個(gè)特殊的棧，在實(shí)現(xiàn)棧的基本功能的基礎(chǔ)上闷旧，實(shí)現(xiàn)返回棧中最小元素的操作
實(shí)例3：如何僅用隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu)长豁？如何僅用棧結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)？
實(shí)例4：貓狗隊(duì)列
實(shí)例5：轉(zhuǎn)圈打印矩陣
實(shí)例6：旋轉(zhuǎn)正方形矩陣
實(shí)例7：反轉(zhuǎn)單向和雙向鏈表
實(shí)例8：“之”字形打印矩陣
實(shí)例9：在行列都排好序的矩陣中找數(shù)
實(shí)例10：打印兩個(gè)有序鏈表的公共部分
實(shí)例11：判斷一個(gè)鏈表是否為回文結(jié)構(gòu)
實(shí)例12：將單向鏈表按某值劃分成左邊小忙灼、中間相等匠襟、右邊大的形式
實(shí)例13：復(fù)制含有隨機(jī)指針節(jié)點(diǎn)的鏈表
實(shí)例14：兩個(gè)單鏈表相交的一系列問題
實(shí)例1
用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)大小固定的隊(duì)列和棧
/**
* @description: 用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)大小固定的隊(duì)列和棧
*
* 1、數(shù)組實(shí)現(xiàn)棧
* 使用一個(gè)size指針该园，
* 添加元素
* 當(dāng)size != arr.length 時(shí)可以向棧添加元素 size++
* 當(dāng)size == arr.lentth 時(shí)拋出數(shù)組越界異常
* 彈出元素
* 當(dāng)size != arr.length 時(shí)可以從棧頂彈出元素酸舍，size - 1
* 當(dāng)size == arr.lentth 時(shí)拋出數(shù)組越界異常
*
*
* 2、數(shù)組實(shí)現(xiàn)隊(duì)列（這個(gè)難度要比實(shí)現(xiàn)棧高）
* 使用三個(gè)指針
* size
* start -- 表示彈出的元素在隊(duì)列中所處的位置
* end -- 表示新增的元素應(yīng)該在隊(duì)列中所處的位置
*
* @version: 1.0
*/
public class Code_11_ArrayToStackAndQueue {
/**
* 數(shù)組結(jié)構(gòu)實(shí)現(xiàn)大小固定的棧
*/
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;
}
// 彈出棧頂元素并刪除棧頂元素啃勉，這里只是將下標(biāo)前移
public Integer pop() {
if (size == 0)
throw new ArrayIndexOutOfBoundsException("The stack is empty");
return arr[--size];
}
}
// 使用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)一個(gè)隊(duì)列
public static class ArrayQueue {
private Integer[] arr;
private Integer size;
private Integer start; // 拿取一個(gè)數(shù)，拿取的是哪個(gè)位置上的數(shù)
private Integer end; // 代表每次新增數(shù)應(yīng)該存放的位置
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];
}
}
}
實(shí)例2
實(shí)現(xiàn)一個(gè)特殊的棧双妨，在實(shí)現(xiàn)棧的基本功能的基礎(chǔ)上淮阐，再實(shí)現(xiàn)返 回棧中最小元素的操作。
【要求】
1．pop斥难、push枝嘶、getMin操作的時(shí)間復(fù)雜度都是O(1)。
2．設(shè)計(jì)的棧類型可以使用現(xiàn)成的棧結(jié)構(gòu)哑诊。
import org.omg.CORBA.INTERNAL;
import java.util.Stack;
/**
* @description:
* 實(shí)現(xiàn)一個(gè)特殊的棧群扶，在實(shí)現(xiàn)棧的基本功能的基礎(chǔ)上，再實(shí)現(xiàn)返 回棧中最小元素的操作镀裤。
* 【要求】
* 1．pop竞阐、push、getMin操作的時(shí)間復(fù)雜度都是O(1)暑劝。
* 2．設(shè)計(jì)的棧類型可以使用現(xiàn)成的棧結(jié)構(gòu)骆莹。
* @version: 1.0
*/
public class Code_12_GetMinStack {
/**
* 準(zhǔn)備兩個(gè)棧
* 一個(gè)棧用來存依次進(jìn)行的數(shù)據(jù)
* 一個(gè)棧用來存最小值
*
* 兩個(gè)棧存數(shù)據(jù)都是同步的
*/
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();
}
}
/**
* 第二種方式
*
* 也是準(zhǔn)備兩個(gè)棧
* 和第一個(gè)不同的是担猛，minStack 只有在出現(xiàn)比當(dāng)前棧頂小的數(shù)的時(shí)候才向minStack 中添加數(shù)據(jù)
* 也就是兩個(gè)棧添加和彈出元素不是同步的幕垦，
* 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中的棧頂元素時(shí)丢氢，更新minStack的狀態(tài)
// 如果彈出的元素和minStack的棧頂元素一樣則證明是最小值，此時(shí)需要同步彈出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());
}
}
實(shí)例3
如何僅用隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu)先改？
如何僅用棧結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)疚察？
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* @description: 如何僅用隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu)？
* 兩個(gè)隊(duì)列實(shí)現(xiàn)棧
* <p>
* 如何僅用棧結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)仇奶？
* 兩個(gè)棧實(shí)現(xiàn)隊(duì)列
* @version: 1.0
*/
public class Code_13_StackAndQueueConvert {
// 兩個(gè)棧實(shí)現(xiàn)隊(duì)列
// 1貌嫡、必須滿足每次transfer數(shù)據(jù)時(shí)pop隊(duì)列必須是空
// 2、必須滿足每次都transfer完所有數(shù)據(jù)
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 不為空该溯，不能導(dǎo)數(shù)據(jù)
if (!popStack.isEmpty()){
return;
}
while (!pushStack.isEmpty()){
popStack.add(pushStack.pop());
}
}
}
// 兩個(gè)隊(duì)列實(shí)現(xiàn)棧結(jié)構(gòu)
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){ // 只剩一個(gè)數(shù)停止
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;
}
}
}
實(shí)例4
貓狗隊(duì)列 【題目】 寵物岛抄、狗和貓的類如下：
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");
}
}
實(shí)現(xiàn)一種狗貓隊(duì)列的結(jié)構(gòu)，要求如下： 用戶可以調(diào)用add方法將cat類或dog類的 實(shí)例放入隊(duì)列中狈茉； 用戶可以調(diào)用pollAll方法夫椭，將隊(duì)列中所有的實(shí)例按照進(jìn)隊(duì)列 的先后順序依次彈出； 用戶可以調(diào)用pollDog方法论皆，將隊(duì)列中dog類的實(shí)例按照 進(jìn)隊(duì)列的先后順序依次彈出益楼； 用戶可以調(diào)用pollCat方法，將隊(duì)列中cat類的實(shí) 例按照進(jìn)隊(duì)列的先后順序依次彈出点晴； 用戶可以調(diào)用isEmpty方法感凤，檢查隊(duì)列中是 否還有dog或cat的實(shí)例； 用戶可以調(diào)用isDogEmpty方法粒督，檢查隊(duì)列中是否有dog 類的實(shí)例陪竿； 用戶可以調(diào)用isCatEmpty方法，檢查隊(duì)列中是否有cat類的實(shí)例屠橄。
import java.util.LinkedList;
import java.util.Queue;
/**
* @description: 貓狗隊(duì)列
*
* 貓狗隊(duì)列 【題目】 寵物族跛、狗和貓的類如下：
* 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"); } }
* 實(shí)現(xiàn)一種狗貓隊(duì)列的結(jié)構(gòu)，要求如下： 用戶可以調(diào)用add方法將cat類或dog類的 實(shí)例放入隊(duì)列中锐墙；
* 用戶可以調(diào)用pollAll方法礁哄，將隊(duì)列中所有的實(shí)例按照進(jìn)隊(duì)列 的先后順序依次彈出娜搂；
* 用戶可以調(diào)用pollDog方法亚脆，將隊(duì)列中dog類的實(shí)例按照 進(jìn)隊(duì)列的先后順序依次彈出；
* 用戶可以調(diào)用pollCat方法芙代，將隊(duì)列中cat類的實(shí) 例按照進(jìn)隊(duì)列的先后順序依次彈出之拨；
* 用戶可以調(diào)用isEmpty方法茉继，檢查隊(duì)列中是 否還有dog或cat的實(shí)例；
* 用戶可以調(diào)用isDogEmpty方法蚀乔，檢查隊(duì)列中是否有dog 類的實(shí)例烁竭；
* 用戶可以調(diào)用isCatEmpty方法，檢查隊(duì)列中是否有cat類的實(shí)例
*/
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");
}
}
/**
* 實(shí)際進(jìn)入貓狗隊(duì)列的實(shí)體
*/
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();
}
}
// 貓狗隊(duì)列
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());
}
}
}
實(shí)例5
轉(zhuǎn)圈打印矩陣
【題目】 給定一個(gè)整型矩陣matrix吉挣，請按照轉(zhuǎn)圈的方式打印它派撕。
例如：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
打印結(jié)果為：1婉弹，2，3腥刹，4马胧，8汉买，12衔峰，16，15蛙粘，14垫卤，13，9出牧， 5穴肘，6，7舔痕，11评抚， 10
【要求】 額外空間復(fù)雜度為O(1)。
所謂的轉(zhuǎn)圈打印矩陣
5_1_轉(zhuǎn)圈打印矩陣示例.png
宏觀思想：按照一圈一圈的去打印伯复，一層一層的處理
5_2_層次處理.png
根據(jù)對角線的兩個(gè)點(diǎn)慨代，左上角和右下角的點(diǎn)（ax,ay）(bx,by)
來推導(dǎo)其他點(diǎn)的變動(dòng)
/**
* @description: 轉(zhuǎn)圈打印矩陣
*
* 轉(zhuǎn)圈打印矩陣 【題目】 給定一個(gè)整型矩陣matrix，請按照轉(zhuǎn)圈的方式打印它啸如。
* 例如：
* 1 2 3 4
* 5 6 7 8
* 9 10 11 12
* 13 14 15 16
* 打印結(jié)果為：
* 1侍匙，2，3叮雳，4想暗，8，12帘不，16说莫，15，14寞焙，13储狭，9， 5棺弊，6晶密，7，11模她， 10
*
* 【要求】 額外空間復(fù)雜度為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) 對角線的倆個(gè)點(diǎn)
int ax = 0;
int ay = 0;
int bx = matrix.length - 1;
int by = matrix[0].length - 1;
// 保證兩點(diǎn)是存在的
while (ax <= bx && ay <= by) {
// 每次傳入兩個(gè)對角線
printEdge(matrix, ax++, ay++, bx--, by--);
System.out.println(); // 每打印一圈換行，方便查看結(jié)果
}
}
public static void printEdge(int[][] matrix, int ax, int ay, int bx, int by) {
// 兩點(diǎn)在一條直線上侈净，不是對角線處理
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);
}
}
實(shí)例6
旋轉(zhuǎn)正方形矩陣
【題目】 給定一個(gè)整型正方形矩陣matrix僧凤，請把該矩陣調(diào)整成 順時(shí)針旋轉(zhuǎn)90度的樣子。
1 2 3
4 5 6
7 8 9
旋轉(zhuǎn)90°
7 4 1
8 5 2
9 6 3
【要求】 額外空間復(fù)雜度為O(1)元扔。
分析：
6_1_矩陣翻轉(zhuǎn)90度坐標(biāo)點(diǎn)變換.png
/**
* @description: 旋轉(zhuǎn)正方形矩陣, 翻轉(zhuǎn)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--);
}
}
// 翻轉(zhuǎn)
public static void rotate(int[][] m, int tR, int tC, int dR, int dC){
int times = dR - tR;// 本圈遍歷次數(shù)
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);
}
}
實(shí)例7
反轉(zhuǎn)單向和雙向鏈表
【題目】 分別實(shí)現(xiàn)反轉(zhuǎn)單向鏈表和反轉(zhuǎn)雙向鏈表的函數(shù)躯保。
【要求】 如果鏈表長度為N，時(shí)間復(fù)雜度要求為O(N)澎语，額外空間 復(fù)雜度要求為O(1)
一途事、反轉(zhuǎn)單向鏈表
雖然對于單向鏈表的寫法已經(jīng)知道了，但是一直對于它處于強(qiáng)行記憶的狀態(tài)擅羞。還好發(fā)現(xiàn)了一篇寫的非常好的文章尸变，作者真的是用心良苦，這里默默的給他點(diǎn)個(gè)贊[圖片上傳失敗...(image-96ff82-1562920150151)]减俏。
原文：https://blog.csdn.net/xyh269/article/details/70238501
現(xiàn)在有一個(gè)單向鏈表如下圖所示：
image
反轉(zhuǎn)后如下所示：
image
接下來解析反轉(zhuǎn)函數(shù)：
image
第一步：next = head.next
將 head.next 賦值給 next 變量召烂，也就是說 next 指向了節(jié)點(diǎn)2，先將節(jié)點(diǎn)2 保存起來娃承。
第二步：head.next = pre
將 pre 變量賦值給 head.next奏夫，即 節(jié)點(diǎn)1 指向了 null
第三步：pre = head
將 head 賦值給了 pre，即 pre 指向節(jié)點(diǎn)1历筝，將節(jié)點(diǎn)1 設(shè)為“上一個(gè)節(jié)點(diǎn)”
第四步：head = next
將 next 賦值給 head酗昼，即 head 指向了節(jié)點(diǎn)2。將節(jié)點(diǎn)2 設(shè)為“頭節(jié)點(diǎn)”
第一次循環(huán)完畢漫谷，進(jìn)入第二次循環(huán)仔雷，如下圖
image
第二次循環(huán)完畢，以此類推舔示！第三次第四次第五次循環(huán)碟婆。最后反轉(zhuǎn)成如下圖
image
看完上面別人的圖，個(gè)人總結(jié)：所謂的反轉(zhuǎn)鏈表其實(shí)就是每次斷開一個(gè)節(jié)點(diǎn)惕稻，置為頭結(jié)點(diǎn)竖共，指向之前已經(jīng)反轉(zhuǎn)好的節(jié)點(diǎn)。
/**
* @description: 反轉(zhuǎn)單向和雙向鏈表
* 【題目】 分別實(shí)現(xiàn)反轉(zhuǎn)單向鏈表和反轉(zhuǎn)雙向鏈表的函數(shù)俺祠。
* 【要求】 如果鏈表長度為N公给，
* 時(shí)間復(fù)雜度要求為O(N)，
* 額外空間 復(fù)雜度要求為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;
}
}
// 反轉(zhuǎn)單向鏈表
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; // 和單向鏈表不同的地方蜘渣，唯一的就是上個(gè)指向
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));
}
}
實(shí)例8
“之”字形打印矩陣
【題目】 給定一個(gè)矩陣matrix淌铐，按照“之”字形的方式打印這 個(gè)矩陣，
例如：
1 2 3 4
5 6 7 8
9 10 11 12
“之”字形打印的結(jié)果為：
1蔫缸，2腿准，5，9拾碌，6吐葱，3街望，4，7弟跑，10灾前，11， 8孟辑，12
【要求】 額外空間復(fù)雜度為O(1)哎甲。
之字形打印走位示例
8_1_之字打印矩陣走位.png
之字打印坐標(biāo)變換
8_2_之字打印坐標(biāo)變換.png
如圖：A，B兩點(diǎn)最初在（0,0）點(diǎn)
A(aR, aC) B(bR, bC)
A點(diǎn)坐標(biāo)扑浸，A一直向右前進(jìn)烧给，當(dāng)遇到邊界時(shí)，改為向下前進(jìn)
B點(diǎn)坐標(biāo)喝噪，B一直向下前進(jìn)，當(dāng)遇到邊界時(shí)指么，改為向右前進(jìn)
/**
* @description:
* “之”字形打印矩陣
* 【題目】 給定一個(gè)矩陣matrix酝惧，按照“之”字形的方式打印這 個(gè)矩陣，
* 例如：
* 1 2 3 4
* 5 6 7 8
* 9 10 11 12
*
* “之”字形打印的結(jié)果為：
* 1伯诬，2晚唇，5，9盗似，6哩陕，3，4赫舒，7悍及，10，11接癌， 8心赶，12
* 【要求】 額外空間復(fù)雜度為O(1)。
*
* @version: 1.0
*/
public class Code_18_ZigZagPrintMatrix {
public static void zigZagPrintMatrix(int[][] matrix) {
// A點(diǎn)坐標(biāo)缺猛，A一直向右前進(jìn)缨叫，當(dāng)遇到邊界時(shí)，改為向下前進(jìn)
int aR = 0;
int aC = 0;
// B點(diǎn)坐標(biāo)荔燎，B一直向下前進(jìn)耻姥，當(dāng)遇到邊界時(shí)，改為向右前進(jìn)
int bR = 0;
int bC = 0;
// 下前進(jìn)邊界有咨，即總行
int enbR = matrix.length - 1;
int enbC = matrix[0].length - 1; // 右前進(jìn)邊界琐簇，即總列
// 向哪個(gè)方向進(jìn)行打印標(biāo)志
boolean fromUp = false;
// 結(jié)束打印條件：
// 以A點(diǎn)分析,A點(diǎn)前進(jìn)路線是 A--> 右 --> 遇邊界 --> 下
// 當(dāng)A--> 下 遇到邊界時(shí)，就是結(jié)束之時(shí)
// 同理摔吏，以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);
}
}
實(shí)例9
在行列都排好序的矩陣中找數(shù)
【題目】 給定一個(gè)有N*M的整型矩陣matrix和一個(gè)整數(shù)K橡娄， matrix的每一行和每一 列都是排好序的癣籽。
實(shí)現(xiàn)一個(gè)函數(shù)，判斷K 是否在matrix中筷狼。
例如：
0 1 2 5
2 3 4 7
4 4 4 8
5 7 7 9
如果K為7，返回true塑顺；
如果K為6严拒，返 回false裤唠。
【要求】 時(shí)間復(fù)雜度為O(N+M)，額外空間復(fù)雜度為O(1)航瞭。
行列都排好序的矩陣中找數(shù)_坐標(biāo)變換
9_1_行列都排好序的矩陣中找數(shù)_坐標(biāo)變換.png
從右上角點(diǎn)(R, C)出發(fā)開始遍歷查找
終止條件是查找到目標(biāo)數(shù)或者當(dāng)前點(diǎn)到達(dá)了左下角的
最后一個(gè)點(diǎn)依然沒有找到目標(biāo)數(shù)沧奴，停止
當(dāng)前點(diǎn)小于 K (如圖2,圖3)
R++
當(dāng)前點(diǎn)大于 K
C--
當(dāng)前點(diǎn)等于 k
返回true
/**
* @description: 在行列都排好序的矩陣中找數(shù)
*
* 【題目】
* 給定一個(gè)有N*M的整型矩陣matrix和一個(gè)整數(shù)K滔吠， matrix的每一行和每一 列都是排好序的挠日。
* 實(shí)現(xiàn)一個(gè)函數(shù)嚣潜，判斷K 是否在matrix中。
* 例如：
* 0 1 2 5
* 2 3 4 7
* 4 4 4 8
* 5 7 7 9
* 如果K為7只冻，返回true；
* 如果K為6喜德，返 回false。
* 【要求】 時(shí)間復(fù)雜度為O(N+M)航棱，額外空間復(fù)雜度為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;
// 從右上角點(diǎn)出發(fā)開始遍歷查找 (R, C)
int R = 0;
int C = matrix[0].length - 1;
// 終止條件是查找到目標(biāo)數(shù)或者當(dāng)前點(diǎn)到達(dá)了左下角的最后一個(gè)點(diǎn)依然沒有找到目標(biāo)數(shù)秕豫，停止
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));
}
}
實(shí)例10
打印兩個(gè)有序鏈表的公共部分
【題目】 給定兩個(gè)有序鏈表的頭指針head1和head2馁蒂，打印兩個(gè)鏈表的公共部分。
思路：類似外排的方式進(jìn)行遍歷兩個(gè)鏈表
/**
* @description: 打印兩個(gè)有序鏈表的公共部分
* 【題目】 給定兩個(gè)有序鏈表的頭指針head1和head2，打印兩個(gè) 鏈表的公共部分沮脖。
* @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;
}
}
// 打印兩個(gè)有序鏈表公共部分
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);
}
}
實(shí)例11
判斷一個(gè)鏈表是否為回文結(jié)構(gòu)
【題目】 給定一個(gè)鏈表的頭節(jié)點(diǎn)head勺届，請判斷該鏈表是否為回 文結(jié)構(gòu)。
例如：
1->2->1胚膊，返回true。
1->2->2->1喻犁，返回true还栓。
15->6->15剩盒，返回true。
1->2->3身隐，返回false。
進(jìn)階： 如果鏈表長度為N垢揩，時(shí)間復(fù)雜度達(dá)到O(N)，額外空間復(fù)雜 度達(dá)到O(1)锋勺。
思路：回文結(jié)構(gòu)，就是鏡面反射
第一種思路：遍歷鏈表苏章，將節(jié)點(diǎn)存入棧中，需要 n extra space
再次遍歷鏈表撑瞧，和棧中每次彈出的節(jié)點(diǎn)進(jìn)行比較
第二種思路：快慢指針订咸，遍歷鏈表找到中間節(jié)點(diǎn)（奇數(shù)鏈表找到中間的前一個(gè)節(jié)點(diǎn)）脏嚷，然后將中間節(jié)點(diǎn)之后的節(jié)點(diǎn)存入棧中，需要 n/2 extra space
再次遍歷鏈表趾唱，和棧中每次彈出的節(jié)點(diǎn)進(jìn)行比較，棧中節(jié)點(diǎn)比較完悠咱，只要沒有不同的節(jié)點(diǎn)，則回文鏈表眼坏。
第三種思路：O(1) 空間復(fù)雜度
1 -> 2 -> 3 -> 2 -> 1
快慢指針找到中間節(jié)點(diǎn)
將中間節(jié)點(diǎn)之后的鏈表進(jìn)行逆序
從兩端開始遍歷，任意一個(gè)到達(dá)null時(shí)停止，在這個(gè)過程中，如果沒有不同節(jié)點(diǎn)肃廓，則回文結(jié)構(gòu)
最后復(fù)原原鏈表結(jié)構(gòu)
import java.util.Stack;
/**
* @description: 判斷一個(gè)鏈表是否為回文結(jié)構(gòu)
* 【題目】 給定一個(gè)鏈表的頭節(jié)點(diǎn)head，請判斷該鏈表是否為回 文結(jié)構(gòu)哀蘑。
* 例如： 1->2->1合溺，返回true。
* 1->2->2->1睛约，返回true。
* 15->6->15膀值，返回true。
* 1->2->3翘狱，返回false。
* 進(jìn)階： 如果鏈表長度為N茬缩，時(shí)間復(fù)雜度達(dá)到O(N)，額外空間復(fù)雜 度達(dá)到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) 的空間復(fù)雜度
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 到達(dá)終點(diǎn)，即n2 不能滿足走下一步（一次跳兩個(gè)節(jié)點(diǎn)）
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
// 存儲(chǔ)后半截到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; // 輔助反轉(zhuǎn)鏈表
while (n2 != null){
help = n2.next;
n2.next = n1;
n1 = n2;
n2 = help;
}
help = n1; // 記錄最后一個(gè)節(jié)點(diǎn)
n2 = head; // n2 指向違反轉(zhuǎn)鏈表的頭結(jié)點(diǎn)
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
}
// 記錄中心點(diǎn)位置
n1 = help.next;
// 恢復(fù)為原鏈表結(jié)構(gòu)
help.next = null;
while(n1 != null){
n2 = n1.next;
n1.next = help;
help = n1;
n1 = n2;
}
return res;
/*
Code_17_RotateList_RotateDoubleList
反轉(zhuǎn)鏈表抄谐，核心步驟
Node pre = null;
Node next = null;
while (head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre; // pre 是反轉(zhuǎn)后的鏈表的頭結(jié)點(diǎn)
*/
}
// 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("=========================");
}
}
實(shí)例12
將單向鏈表按某值劃分成左邊小、中間相等憎茂、右邊大的形式
【題目】 給定一個(gè)單向鏈表的頭節(jié)點(diǎn)head，節(jié)點(diǎn)的值類型是整型拳氢，再給定一個(gè) 整 數(shù)pivot。
實(shí)現(xiàn)一個(gè)調(diào)整鏈表的函數(shù)留特，將鏈表調(diào)整為左部分都是值小于 pivot 的節(jié)點(diǎn)，中間部分都是值等于pivot的節(jié)點(diǎn)，右部分都是值大于 pivot的節(jié)點(diǎn)蒙兰。 除這個(gè)要求外采缚，對調(diào)整后的節(jié)點(diǎn)順序沒有更多的要求篡帕。
例如：鏈表9->0->4->5>1拢军，pivot=3茉唉。
調(diào)整后鏈表可以是1->0->4->9->5，也可以是0->1->9->5->4懂傀。
總 之，滿 足左部分都是小于3的節(jié)點(diǎn)，中間部分都是等于3的節(jié)點(diǎn)（本例中這個(gè)部 分為空）闪水，右部分都是大于3的節(jié)點(diǎn)即可。對某部分內(nèi)部的節(jié)點(diǎn)順序不做 要求。
進(jìn)階： 在原問題的要求之上再增加如下兩個(gè)要求每强。
在左、中、右三個(gè)部分的內(nèi)部也做順序要求门坷，要求每部分里的節(jié)點(diǎn)從左 到右的 順序與原鏈表中節(jié)點(diǎn)的先后次序一致冻晤。
例如：鏈表9->0->4->5->1，pivot=3温数。
調(diào)整后的鏈表是0->1->9->4->5。
在滿足原問題要求的同時(shí)，左部分節(jié)點(diǎn)從左到 右為0冕屯、1。
在原鏈表中也 是先出現(xiàn)0，后出現(xiàn)1念颈；中間部分在本例中為空跺撼，不再 討論肌括；
右部分節(jié)點(diǎn) 從左到右為9谍夭、4菜谣、5媳危。在原鏈表中也是先出現(xiàn)9，然后出現(xiàn)4暮蹂， 最后出現(xiàn)5。
如果鏈表長度為N，時(shí)間復(fù)雜度請達(dá)到O(N)棠枉，額外空間復(fù)雜度請達(dá)到O(1)。
/**
* @description: 將單向鏈表按某值劃分成左邊小荞估、中間相等褂删、右邊大的形式
*
* 【題目】 給定一個(gè)單向鏈表的頭節(jié)點(diǎn)head，節(jié)點(diǎn)的值類型是整型，再給定一個(gè) 整 數(shù)pivot。
* 實(shí)現(xiàn)一個(gè)調(diào)整鏈表的函數(shù)彼宠，將鏈表調(diào)整為左部分都是值小于 pivot 的節(jié)點(diǎn)决记，
* 中間部分都是值等于pivot的節(jié)點(diǎn)按价，右部分都是值大于 pivot的節(jié)點(diǎn)笙瑟。
* 除這個(gè)要求外楼镐，對調(diào)整后的節(jié)點(diǎn)順序沒有更多的要求。
* 例如：鏈表9->0->4->5>1往枷，pivot=3框产。 調(diào)
* 整后鏈表可以是
* 1->0->4->9->5错洁，
*
* 也可以是
* 0->1->9->5->4秉宿。
*
* 總 之，滿 足左部分都是小于3的節(jié)點(diǎn)屯碴，中間部分都是等于3的節(jié)點(diǎn)（本例中這個(gè)部 分為空）描睦，
* 右部分都是大于3的節(jié)點(diǎn)即可。對某部分內(nèi)部的節(jié)點(diǎn)順序不做 要求导而。
* 進(jìn)階： 在原問題的要求之上再增加如下兩個(gè)要求忱叭。 在左、中今艺、右三個(gè)部分的內(nèi)部也做順序要求韵丑，
* 要求每部分里的節(jié)點(diǎn)從左 到右的 順序與原鏈表中節(jié)點(diǎn)的先后次序一致。 例如：鏈表9->0->4->5->1虚缎，pivot=3撵彻。
* 調(diào)整后的鏈表是0->1->9->4->5。 在滿足原問題要求的同時(shí)，左部分節(jié)點(diǎn)從左到 右為0陌僵、1轴合。
* 在原鏈表中也 是先出現(xiàn)0，后出現(xiàn)1碗短；中間部分在本例中為空值桩，不再 討論；右部分節(jié)點(diǎn) 從左到右為9豪椿、4、5携栋。
* 在原鏈表中也是先出現(xiàn)9搭盾，然后出現(xiàn)4， 最后出現(xiàn)5婉支。
*
* 如果鏈表長度為N鸯隅，時(shí)間復(fù)雜度請達(dá)到O(N)，額外空間復(fù)雜度請達(dá)到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）的空間復(fù)雜度來轉(zhuǎn)換為數(shù)組，進(jì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;
// 裝載進(jìn)數(shù)組
while (cur != null){
arr[i++] = cur;
cur = cur.next;
}
// 按照荷蘭國旗方式進(jìn)行分區(qū)
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
// 每次從鏈表中彈出首節(jié)點(diǎn)跟畅，存放到這三個(gè)區(qū)域鏈表中
while (head != null) {
next = head.next;
head.next = null; // 彈出首節(jié)點(diǎn)
if (head.value > pivot){
if (bH == null){
bH = head;
bT = head;
} else {
bT.next = head;
bT = head; // 尾節(jié)點(diǎn)指向新節(jié)點(diǎn)
}
} 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
// 合并小區(qū)域和等區(qū)域
if(sT != null) {
sT.next = eH;
eT = eT == null ? sT : eT;
}
// 合并等于區(qū)域和大區(qū)域
if (eT != null) {
eT.next = bH;
}
// 小區(qū)域不為空 ？（返回小區(qū)域+等于區(qū)域+大區(qū)域鏈總鏈） ： （返回等于區(qū)域+大區(qū)域鏈）
// 等于區(qū)域不為空 溶推？（返回等于區(qū)域+大區(qū)域鏈總鏈）：（大于區(qū)域鏈）
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);
}
}
實(shí)例13
復(fù)制含有隨機(jī)指針節(jié)點(diǎn)的鏈表
【題目】 一種特殊的鏈表節(jié)點(diǎn)類描述如下：
public class Node {
? public int value;
? public Node next;
? public Node rand;
? public Node(int data) { this.value = data; }
}
Node類中的value是節(jié)點(diǎn)值徊件，next指針和正常單鏈表中next指針的意義 一 樣，都指向下一個(gè)節(jié)點(diǎn)蒜危，rand指針是Node類中新增的指針虱痕，這個(gè)指 針可 能指向鏈表中的任意一個(gè)節(jié)點(diǎn)，也可能指向null辐赞。
給定一個(gè)由 Node節(jié)點(diǎn)類型組成的無環(huán)單鏈表的頭節(jié)點(diǎn)head部翘，請實(shí)現(xiàn)一個(gè) 函數(shù)完成 這個(gè)鏈表中所有結(jié)構(gòu)的復(fù)制，并返回復(fù)制的新鏈表的頭節(jié)點(diǎn)响委。
進(jìn)階： 不使用額外的數(shù)據(jù)結(jié)構(gòu)新思，只用有限幾個(gè)變量，且在時(shí)間復(fù)雜度為 O(N) 內(nèi)完成原問題要實(shí)現(xiàn)的函數(shù)晃酒。
思路：
1表牢、忽略random指針，復(fù)制并鏈接每一個(gè)節(jié)點(diǎn)成一個(gè)新鏈
2贝次、遍歷新鏈表崔兴，每次取出兩個(gè)節(jié)點(diǎn)。
根據(jù)原節(jié)點(diǎn)，查找新節(jié)點(diǎn)對應(yīng)的random指針指向的節(jié)點(diǎn)（如圖2）
3敲茄、拆分鏈表
將組合鏈表拆分為復(fù)制鏈表和原鏈表
13_1_復(fù)制含有隨機(jī)指針節(jié)點(diǎn)的鏈表.png
import java.util.HashMap;
/**
* @description: 復(fù)制含有隨機(jī)指針節(jié)點(diǎn)的鏈表
* 【題目】 一種特殊的鏈表節(jié)點(diǎn)類描述如下：
* public class Node {
* public int value;
* public Node next;
* public Node rand;
*
* public Node(int data) { this.value = data; }
* }
* Node類中的value是節(jié)點(diǎn)值位谋，
* next指針和正常單鏈表中next指針的意義 一 樣，都指向下一個(gè)節(jié)點(diǎn)堰燎，
* rand指針是Node類中新增的指針掏父，這個(gè)指 針可 能指向鏈表中的任意一個(gè)節(jié)點(diǎn)，也可能指向null秆剪。
*
* 給定一個(gè)由 Node節(jié)點(diǎn)類型組成的無環(huán)單鏈表的頭節(jié)點(diǎn)head赊淑，
*
* 請實(shí)現(xiàn)一個(gè) 函數(shù)完成 這個(gè)鏈表中所有結(jié)構(gòu)的復(fù)制，并返回復(fù)制的新鏈表的頭節(jié)點(diǎn)仅讽。
*
* 進(jìn)階： 不使用額外的數(shù)據(jù)結(jié)構(gòu)陶缺，只用有限幾個(gè)變量，且在時(shí)間復(fù)雜度為 O(N) 內(nèi)完成原問題要實(shí)現(xiàn)的函數(shù)洁灵。
* @version: 1.0
*/
public class Code_23_CopyListWithRandom {
public static class Node {
public int value;
public Node next;
public Node rand; // 隨機(jī)指針
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; // 每次都是指向下一次循環(huán)的頭結(jié)點(diǎn)饱岸，即保存下一次循環(huán)的頭結(jié)點(diǎn)位置
// 復(fù)制每個(gè)節(jié)點(diǎn)，并連接成為一個(gè)新鏈
while (cur != null) {
next = cur.next; // 保留下一個(gè)頭結(jié)點(diǎn)位置
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next; // 重置遍歷的頭結(jié)點(diǎn)
}
// 拷貝random 節(jié)點(diǎn)
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("=========================");
}
}
實(shí)例14
兩個(gè)單鏈表相交的一系列問題
【題目】 在本題中徽千，單鏈表可能有環(huán)苫费，也可能無環(huán)。
給定兩個(gè) 單鏈表的頭節(jié)點(diǎn) head1和head2双抽，這兩個(gè)鏈表可能相交百框，也可能 不相交。
請實(shí)現(xiàn)一個(gè)函數(shù)荠诬， 如果兩個(gè)鏈表相交琅翻，請返回相交的 第一個(gè)節(jié)點(diǎn)；
如果不相交柑贞，返回null 即可方椎。
要求：如果鏈表1 的長度為N，鏈表2的長度為M钧嘶，時(shí)間復(fù)雜度請達(dá)到 O(N+M)棠众，額外 空間復(fù)雜度請達(dá)到O(1)。
思路
這道題可以拆分為幾道題
1有决、單鏈表是否有環(huán)
2闸拿、兩個(gè)無環(huán)單鏈表是否相交
3、兩個(gè)有環(huán)單鏈表是否相交
這里先說說不考慮空間復(fù)雜度做法
最快做法书幕，需要額外的空間新荤，使用哈希表 HashSet<Node>
1、判斷單鏈表是否有環(huán)
將鏈表head節(jié)點(diǎn)循環(huán)存入 哈希表台汇，哈希表返回false苛骨，成環(huán)
通過哈希表來進(jìn)行快速查找到環(huán)節(jié)點(diǎn)
HashSet<Node> set
HashSet集合特點(diǎn)：不能存儲(chǔ) Key 相同的值骂租，
即存入值時(shí)返回false避咆，則證明set里面已經(jīng)存在了這個(gè)節(jié)點(diǎn)
遍歷鏈表低斋，依次將鏈表的節(jié)點(diǎn)存放到HashSet
遇到HashSet返回false時(shí)静秆，記錄這個(gè)節(jié)點(diǎn)，此節(jié)點(diǎn)就是環(huán)節(jié)點(diǎn)严衬，并返回
set ---> 1 --->true
set ---> 2 --->true
set ---> 3 --->true
set ---> 4 --->true
set ---> 5 --->true
set ---> 2 --->false --> 返回此節(jié)點(diǎn)
2澄者、判斷兩個(gè)無環(huán)單鏈表是否相交
同理1
通過HashSet查找兩個(gè)無環(huán)鏈表交點(diǎn)
先遍歷head1，將節(jié)點(diǎn)一次存入set
在遍歷head2请琳，遇到存set時(shí)返回false則證明存在交叉點(diǎn)粱挡，返回此交叉點(diǎn)
，head2 遍歷到結(jié)束依然沒有返回false則證明不存在交叉點(diǎn)俄精，返回null
PS：注意：這里說的同一個(gè)節(jié)點(diǎn)抱怔，跟節(jié)點(diǎn)的value值沒有任何關(guān)系，HashSet判斷是否是同一個(gè)節(jié)點(diǎn)嘀倒，比較的是內(nèi)存地址。
哈希表查找是否有環(huán)
14_img_01_哈希表_01_單鏈表是否有環(huán).png
哈希表查找兩個(gè)無環(huán)鏈表交點(diǎn)
14_img_01_哈希表_02_兩個(gè)無環(huán)單鏈表是否有交點(diǎn).png
當(dāng)然局冰，根據(jù)題目要求测蘑，這里空間復(fù)雜度要求為O(1), 顯然不能使用上述做法
1、單鏈表是否有環(huán)
通過快慢指針查找環(huán)節(jié)點(diǎn)
Node f 快節(jié)點(diǎn)：一次跳兩個(gè)節(jié)點(diǎn)
Node s 慢節(jié)點(diǎn)：一次跳一個(gè)節(jié)點(diǎn)
快慢節(jié)點(diǎn)初始都指向 首節(jié)點(diǎn)（如圖1）
循環(huán)遍歷康二，當(dāng)快慢節(jié)點(diǎn)第一次相交時(shí)（如圖5）碳胳，
快節(jié)點(diǎn)重新指向首節(jié)點(diǎn)，慢節(jié)點(diǎn)保持不變（如圖6）
繼續(xù)遍歷沫勿，當(dāng)快慢節(jié)點(diǎn)再一次相交時(shí)（如圖7）
返回此節(jié)點(diǎn)
快慢指針查找環(huán)節(jié)點(diǎn)
14_img_11_快慢指針_01_單鏈表是否有環(huán).png
2挨约、判斷兩個(gè)無環(huán)單鏈表是否相交
不采用哈希表兩個(gè)無環(huán)單鏈表查找交點(diǎn)
采用兩個(gè)變量分別記錄
count 記錄鏈表的長度
tail 記錄尾節(jié)點(diǎn)位置
先遍歷head1 記錄count1 和tail1
再遍歷head2 記錄count2 和tail2
比較 if(tail1 != tail2) return null
因?yàn)槭菃捂湵恚粲薪稽c(diǎn)产雹，則尾節(jié)點(diǎn)一定相同诫惭。
比較兩個(gè)鏈表長度
這里假設(shè) head1 比 head2 長
count = count1 - count2
讓head1 比head2 多走count 步（如圖1），然后head1和head2同時(shí)進(jìn)行遍歷
當(dāng)兩個(gè)鏈表相交時(shí)返回交點(diǎn)（如圖2）
當(dāng)兩個(gè)鏈表遍歷完都無交點(diǎn)則返回null
兩個(gè)無環(huán)單鏈表是否相交
14_img_12_快慢指針_01_兩個(gè)無環(huán)單鏈表是否有交點(diǎn).png
接下來考慮兩個(gè)有環(huán)單鏈表相交問題
PS：注意蔓挖，一個(gè)有環(huán)夕土，一個(gè)無環(huán)，不存在交點(diǎn)瘟判，因?yàn)槭菃捂湵怼?/p>
14_img_13_快慢指針_01_兩個(gè)有環(huán)單鏈表相交有三種拓?fù)浣Y(jié)構(gòu).png
兩個(gè)有環(huán)鏈表查找交叉點(diǎn)
兩個(gè)有環(huán)鏈表有三種拓?fù)浣Y(jié)構(gòu)：各自成環(huán)（無交點(diǎn)）怨绣，相交于環(huán)外，相交于環(huán)內(nèi)
各自成環(huán)拷获、相交于環(huán)外篮撑、內(nèi)判斷方式：根據(jù)前面返回的交點(diǎn)（loop1、loop2）判斷
if(loop1 == loop2) 環(huán)外
if(loop1 != loop2) 環(huán)內(nèi) 或者 各自成環(huán)
loop1繼續(xù)遍歷匆瓜，遍歷完畢沒有找到loop2赢笨，則是各自成環(huán)未蝌。
loop1繼續(xù)遍歷，遍歷找到loop2點(diǎn)质欲，則是環(huán)內(nèi)
返回loop1树埠，loop2都可以作為第一個(gè)相交的節(jié)點(diǎn)
相交于環(huán)外
? 處理方式：按照兩個(gè)無環(huán)單鏈表相交節(jié)點(diǎn)的查找方式進(jìn)行查找
? 處理范圍：head1~loop1 head2~loop2 （如圖3）
14_img_14_快慢指針_01_兩個(gè)無環(huán)單鏈表相交有三種拓?fù)浣Y(jié)構(gòu).png
/**
* @description: 兩個(gè)單鏈表相交的一系列問題
* 【題目】 在本題中，單鏈表可能有環(huán)嘶伟，也可能無環(huán)怎憋。
* 給定兩個(gè) 單鏈表的頭節(jié)點(diǎn) head1和head2，這兩個(gè)鏈表可能相交九昧，也可能 不相交绊袋。
* 請實(shí)現(xiàn)一個(gè)函數(shù)， 如果兩個(gè)鏈表相交铸鹰，請返回相交的 第一個(gè)節(jié)點(diǎn)癌别；
* 如果不相交，返回null 即可蹋笼。 要
*
* 求：如果鏈表1 的長度為N展姐，鏈表2的長度為M，時(shí)間復(fù)雜度請達(dá)到 O(N+M)剖毯，額外 空間復(fù)雜度請達(dá)到O(1)
*
* 這道題可以拆分為幾道題
*
* 1圾笨、單鏈表是否有環(huán)
* 2、兩個(gè)無環(huán)單鏈表是否相交
* 3逊谋、兩個(gè)有環(huán)單鏈表是否相交
*
* 最快做法擂达，需要額外的空間，使用哈希表 HashSet<Node>
*
* 1胶滋、判斷單鏈表是否有環(huán)
* 將鏈表head節(jié)點(diǎn)循環(huán)存入 哈希表板鬓，哈希表返回false，成環(huán)
*
* 2究恤、判斷兩個(gè)無環(huán)單鏈表是否相交
* 同理 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);
}
// 不存在一個(gè)有環(huán)一個(gè)無環(huán)結(jié)構(gòu)相交
return null;
}
/**
* 雙指針判斷鏈表是否有環(huán)俭令，并返回第一個(gè)環(huán)節(jié)點(diǎn)
* @return 第一個(gè)環(huán)節(jié)點(diǎn)
*/
public static Node getLoopNode(Node head){
if(head == null && head.next == null && head.next.next == null) // 最少三個(gè)節(jié)點(diǎn)成環(huán)
return null;
Node s = head.next;
Node f = head.next.next;
while (s != f) { // s等于f時(shí)兩指針第一次相交，返回
if (f.next == null || f.next.next == null)
return null;// 快指針到達(dá)了尾節(jié)點(diǎn)null部宿，證明不成環(huán)
s = s.next;
f = f.next.next;
}
f = head; // 快指針從頭開始遍歷唤蔗，此時(shí)跨步和慢指針一樣
while (f != s){
f = f.next;
s = s.next;
}
return s; // or f
}
/**
* 判斷兩個(gè)無環(huán)單鏈表是否相交
* @return 第一次相交節(jié)點(diǎn) 或者 null
*/
public static Node noLoop(Node head1, Node head2){
if (head1 == null || head2 == null)
return null; // 任意一個(gè)單鏈表null，不存在交點(diǎn)
Node cur1 = head1;
Node cur2 = head2;
int count = 0; // 記錄單鏈表長度
// 遍歷單鏈表head1窟赏，記錄鏈表長度妓柜，和尾節(jié)點(diǎn)
while (cur1 != null){
count++;
cur1 = cur1.next;
}
while (cur2 != null){
count--;
cur2 = cur2.next;
}
if (cur1 != cur2) return null;// 如果兩個(gè)單鏈表的尾節(jié)點(diǎn)不同，一定不相交
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
/**
* 兩個(gè)有環(huán)單鏈表是否相交
* @param head1
* @param loop1 第一個(gè)鏈表環(huán)節(jié)點(diǎn)
* @param head2
* @param loop2 第二個(gè)鏈表環(huán)節(jié)點(diǎn)
* @return 第一個(gè)相交節(jié)點(diǎn)
*
* 兩個(gè)有環(huán)鏈表有三種拓?fù)浣Y(jié)構(gòu)：各自成環(huán)不相交涯穷，環(huán)外相交棍掐，環(huán)內(nèi)相交
*
* loop1 == loop2 true，環(huán)外相交
* false拷况，循環(huán)遍歷head1 作煌，從loop1 開始遍歷掘殴，到再一次經(jīng)過loop1，
* 若找到loop2 節(jié)點(diǎn)粟誓，相交 返回loop1 或者 loop2 ----> 環(huán)內(nèi)
* 若沒找到loop2奏寨， 不相交 各自成環(huán)
*/
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
if (loop1 == loop2) { // 環(huán)外
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 { // 各自成環(huán)不相交或者環(huán)內(nèi)相交
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("兩個(gè)無環(huán)單鏈表：" + 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("兩個(gè)有環(huán)單鏈表，且是環(huán)外結(jié)構(gòu)：" + 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("兩個(gè)有環(huán)單鏈表鹰服，且是環(huán)內(nèi)結(jié)構(gòu)：" + getIntersectNode(head1, head2).value);
}
}
注：以上皆是學(xué)習(xí)算法課程總結(jié)
