算法<初级> – 第二章 队列、栈、哈希表相关问题

题目一 用数组实现大小固定的队列和栈（一面题）

数组实现大小固定栈

/***
*   size是对头索引（initSize是固定大小） 也是当前栈大小
*   size=下个进队index
*   size-1=下个出队index
*   size==initSize时队满 判满
*   size==0时队空 判空
***/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 queue is full");
}
arr[size++] = obj;
}    public Integer pop() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
return arr[--size];
}
}

数组实现大小固定队列

/***
*   size当前队列大小；用size关联first/last更加方便
*   last队尾
*   first队头
*   循环队列：
*   first = first == arr.length - 1 ? 0 : first + 1;
*   last = last == arr.length - 1 ? 0 : last + 1;
***/
public static class ArrayQueue {
private Integer[] arr;
private Integer size;
private Integer first;
private Integer last;public ArrayQueue(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
size = 0;
first = 0;
last = 0;
}public Integer peek() { //查看队头元素
if (size == 0) {
return null;
}
return arr[first];
}public void push(int obj) {    //进队
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
size++;
arr[last] = obj;
last = last == arr.length - 1 ? 0 : last + 1; //循环队列
}public Integer poll() {      //出队弹出
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
size--;
int tmp = first;
first = first == arr.length - 1 ? 0 : first + 1;
return arr[tmp];
}
}

题目二：实现一个特殊的栈

• 题目表述：实现一个特殊的栈，在实现栈的基本功能上再实现返回栈最小值的操作。

  【要求】：

  1. pop、push、geiMin操作的时间复杂度O(1)

  2. 设计的栈类型可以使用现成的栈结构

• 思想：

  • 基本栈的结构 – 双向链表/动态数组
  • 思路一：构造两个栈，一个data栈，一个min栈。data栈压栈入栈元素，同时min栈压栈最小元素（每来一个元素与栈顶元素比较，谁小压谁）。出栈则两个栈同时弹出
    • data：||32415
    • min：||32211
  • 思路二：构造两个栈，data / min栈。data栈压入栈元素，min栈顶元素比较，小则同时压入min栈，否则不压栈。出栈则比较，data栈出栈元素=min栈顶元素时，min栈出栈。
    • data：||32415
    • min：||321

思路一

• 算法实现（Java）

public static class MyStack1 {           //思路一
private Stack<Integer> stackData;
private Stack<Integer> stackMin;public MyStack1() {
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);
}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();
}
}

思路二

• 算法实现（Java）

public static class MyStack2 {          //思路二
private Stack<Integer> stackData;
private Stack<Integer> stackMin;public MyStack2() {
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);
} else {
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
this.stackMin.pop();
return this.stackData.pop();
}public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}

题目三：队列实现栈 / 栈实现队列（灵活应用）

队列实现栈

• 思路
  • 用两个队列实现栈
  • 序列先全进第一个队列，进行以下操作：
    • 保留最后一个数其他元素全部出队列，进入第二个队列
    • 把第一个队列的值输出（即让最后进来的最先出去）
    • 之后第二个队列同样操作进入第一个队列，把最后一个元素输出
• 演示
  • 54321 空 —> 5 4321 输出5
  • 空 4321 —> 321 4 输出4

+算法实现（Java）

public static class TwoQueuesStack {
private Queue<Integer> queue;
private Queue<Integer> help;public TwoQueuesStack() {
queue = new LinkedList<Integer>();
help = new LinkedList<Integer>();
}public void push(int pushInt) {
queue.add(pushInt);
}public int peek() {     //得到栈顶元素
if (queue.isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
while (queue.size() != 1) {
help.add(queue.poll());
}
int res = queue.poll();     //res为最后一个入队元素
help.add(res);
swap();     //两个栈引用交换一下
return res;
}public int pop() {
if (queue.isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
while (queue.size() != 1) {
help.add(queue.poll());
}
int res = queue.poll();
swap();
return res;
}private void swap() {
Queue<Integer> tmp = help;
help = queue;
queue = tmp;
}}

栈实现队列

• 思路
  • 用两个栈实现队列：第一个栈专做push，第二个栈专做pop
  • 直接入第一个栈，全部倒入第二个栈，第二个栈再全部出栈，即可实现先进先出
  • 一栈倒二栈时机：
    1. 当pop栈中非空时，push栈不能倒
    2. pop栈为空时push倒，倒必须一次性倒完
  • 只要满足上述两个条件，无论倒数操作发生在什么时候，都一定对
• 算法实现（Java）

public static class TwoStacksQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}public void push(int pushInt) {
stackPush.push(pushInt);
}public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
} else if (stackPop.empty()) {          //倒数操作
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
} else if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}

题目四：猫狗队列

• 题目表述：有如下猫类狗类，实现一个猫狗队列结构
  • add方法将cat / dog类实例入队
  • pollAll方法将所有实例出队
  • pollDog方法将所有狗实例出队
  • pollCat方法同理
  • isEmpty方法判断是否还有猫狗实例
  • isDogEmpty方法同理
  • isCatEmpty方法同理
• 猫狗类型：

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");
}
}

• 思路

  • 猫狗各一个队列，队列中用封装类PetEnterQueue，封装了一个pet类和一个count标志。
  • all系列函数则根据count标志的大小来决定同一队头谁先出

• 算法实现（Java）

public static class PetEnterQueue {//为了不修改底层类，封装进一个新类
private Pet pet;
private long count;//标记自己是几号，衡量猫狗谁先出public PetEnterQueue(Pet pet, long count) {
this.pet = pet;
this.count = count;
}public Pet getPet() {
return this.pet;
}public long getCount() {
return this.count;
}public String getEnterPetType() {
return this.pet.getPetType();
}
}public static class DogCatQueue {
private Queue<PetEnterQueue> dogQ;
private Queue<PetEnterQueue> catQ;
private long count;public DogCatQueue() {
this.dogQ = new LinkedList<PetEnterQueue>();
this.catQ = new LinkedList<PetEnterQueue>();
this.count = 0;
}public void add(Pet pet) {
if (pet.getPetType().equals("dog")) {
this.dogQ.add(new PetEnterQueue(pet, this.count++));
} else if (pet.getPetType().equals("cat")) {
this.catQ.add(new PetEnterQueue(pet, this.count++));
} else {
throw new RuntimeException("err, not dog or cat");
}
}public Pet pollAll() {
if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
return this.dogQ.poll().getPet();
} else {
return this.catQ.poll().getPet();
}
} else if (!this.dogQ.isEmpty()) {
return this.dogQ.poll().getPet();
} else if (!this.catQ.isEmpty()) {
return this.catQ.poll().getPet();
} else {
throw new RuntimeException("err, queue is empty!");
}
}public Dog pollDog() {
if (!this.isDogQueueEmpty()) {
return (Dog) this.dogQ.poll().getPet();
} else {
throw new RuntimeException("Dog queue is empty!");
}
}public Cat pollCat() {
if (!this.isCatQueueEmpty()) {
return (Cat) this.catQ.poll().getPet();
} else
throw new RuntimeException("Cat queue is empty!");
}public boolean isEmpty() {
return this.dogQ.isEmpty() && this.catQ.isEmpty();
}public boolean isDogQueueEmpty() {
return this.dogQ.isEmpty();
}public boolean isCatQueueEmpty() {
return this.catQ.isEmpty();
}}

哈希表

• 增删改查默认时间复杂度O(1)，但是常数项比较大 – 因为哈希函数在算值的时候代价比较大

哈希函数hashmap

• 性质
  1. 输入域无限，输出域有限
  2. 哈希函数不是随机函数，相同输入一定得到相同输出 same input same out
  3. 哈希碰撞：不同的输入也可能得到相同的输出 diff input same out
  4. 哈希函数的离散性：虽然性质①，但是不同的输入在输出域上得到的返回值会均匀分布（最重要性质）—> 用来打乱输入规律

哈希表/散列表

• 经典实现结构：由输出域组成的一组数组，每个值对应一组输入值链表。输入值根据哈希函数得到输出域上对应的某值，然后挂载在数组值的链表上。
• 哈希表扩容
  • 当挂载链表太长时，可以选择哈希表扩容，成倍扩容，时间复杂度可以做到O(1)
  • 可以离线扩容，扩容频率也不频繁
• Java哈希表实现结构：输出域仍然是一组数组，每个值后挂载的是一棵红黑树treemap
• hashset & hashmap
  • 实际上都是哈希表，前者add(key)，后者put(key,value)，value实际上就是key多出的一个伴随数据，并不影响哈希表结构

题目五：设计RandomPool结构

• 题目表述：设计一种结构，在该结构中有如下三个功能，要求时间复杂度O(1)：

  • insert(key)：将某个key加入到该结构，做到不重复加入
  • delete(key)：将原本在结构中的某个key移除
  • getRandom()：等概率随机返回结构中任何一个key

• 思路

  • 直接用哈希表就可以完成，难点的是（有delete情况下的getRandom）
  • 设置两张哈希表，第一个哈希表key是加入的值，value是第几个加入的；第二个哈希表key是第几个加入的，value是加入的值
  • 设置一个index变量，int index=0，每加入一个key，index++
  • insert和delete可以直接在第一个哈希表中完成，第二个哈希表也对应做出相同操作
  • getRandom可以直接随机函数生成一个随机数，但是问题是delete可能会使（第几个加入的）值变成不连续的，导致无法使用随机函数
  • 解决：
    • 每当删除一个key时，先让inedx–，再让index位置上的key（即最后加入的key），覆盖掉要删除的key，原要删除的value不变，把最后加入的key/value行删除。
    • 这样即可让value是一个连续的值，可以直接用随机函数随机get

• 算法实现（Java）

public static class Pool<K> {          //K模板
   private HashMap<K, Integer> keyIndexMap;
   private HashMap<Integer, K> indexKeyMap;
   private int size;   public Pool() {
   this.keyIndexMap = new HashMap<K, Integer>();
   this.indexKeyMap = new HashMap<Integer, K>();
   this.size = 0;
   }   public void insert(K key) {
   if (!this.keyIndexMap.containsKey(key)) {
   this.keyIndexMap.put(key, this.size);
   this.indexKeyMap.put(this.size++, key);
   }
   }   public void delete(K key) {
   if (this.keyIndexMap.containsKey(key)) {
   int deleteIndex = this.keyIndexMap.get(key);
   int lastIndex = --this.size;
   K lastKey = this.indexKeyMap.get(lastIndex);
   this.keyIndexMap.put(lastKey, deleteIndex);
   this.indexKeyMap.put(deleteIndex, lastKey);
   this.keyIndexMap.remove(key);
   this.indexKeyMap.remove(lastIndex);
   }
   }   public K getRandom() {
   if (this.size == 0) {
   return null;
   }
   int randomIndex = (int) (Math.random() * this.size);
   return this.indexKeyMap.get(randomIndex);
   }   }

题目六：转圈打印矩阵（矩阵打印题）

• 题目表述：给定一个整型矩阵matrix，请按照转圈的方式打印它，要求空间复杂度O(1)

  例如：

  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

• 对于矩阵/数组打印题，应该往一种宏观调度的思想，而不要着眼于索引位置的变换。

• 思路：

  • 划定两个点，圈的左上角和右下角，然后一圈一圈的打印输出

  • 打印圈圈printEage()：左上(row1,col1) / 右下(row2,col2) / 目前点(curRow,curCol)

    • 初始化目前点为左上，打印目前点元素；
    • 当curRow<row2时，打印目前点位置元素，curRow++；
    • curRol = row2后，当curCol<col2时，打印目前点位置元素，curCol++；
    • 当目前点到右下点后继续
    • 当curRow>row1时，打印目前点位置元素，curRow–；
    • curRow=row1后，当curCol>col1时，打印目前点位置元素，curCol–；

  • 主函数Matrixprint()：

    • while()打印外圈，打印完后row1++，col1++，row2–，col2–；
    • 跳出条件：左上点<=右下点

• 算法实现（Java）

public static void spiralOrderPrint(int[][] matrix) {
int tR = 0;
int tC = 0;
int dR = matrix.length - 1;
int dC = matrix[0].length - 1;
while (tR <= dR && tC <= dC) {
printEdge(matrix, tR++, tC++, dR--, dC--);
}
}public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
if (tR == dR) { // 只有一行的时候
for (int i = tC; i <= dC; i++) {
System.out.print(m[tR][i] + " ");
}
} else if (tC == dC) { // 只有一列的时候
for (int i = tR; i <= dR; i++) {
System.out.print(m[i][tC] + " ");
}
} else { // n*m矩阵的时候
int curC = tC;
int curR = tR;
while (curC != dC) {
System.out.print(m[tR][curC] + " ");
curC++;
}
while (curR != dR) {
System.out.print(m[curR][dC] + " ");
curR++;
}
while (curC != tC) {
System.out.print(m[dR][curC] + " ");
curC--;
}
while (curR != tR) {
System.out.print(m[curR][tC] + " ");
curR--;
}
}
}

题目七：之字形打印矩阵（矩阵打印题）

• 题目表述

  • 给定一个矩阵matrix按照之字形打印矩阵，要求空间复杂度O(1)

    例如：

    1 2 3 4

    5 6 7 8

    9 10 11 12

    之字形打印结果：1，2 ，5 ，9 ，6 ，3，4，7，10，11，8，12

• 宏观调度就是不拘于矩阵打印的位置变换，而是着眼于单元块/接口这样的设计

• 思路：

  • 两个点，(row1，col1)，（row2，col2）；
  • 打印对角函数printlevel()：传入两个点+控制方向flag
    • flag为正，向斜上打印；flag为负，向斜下打印；
    • 退出条件为：row1越界row2/row2越界row1（col一起变化就不用写了）
  • 主函数控制printZmatrix()：
    • 一开始1点=2点，循环调用打印对角函数
    • 调用一次后，1点向下走，越界后向右走；2点向右走，越界后向下走；同步row++/col++
    • 每次flag打印完后取反，初始为负；
    • 跳出打印条件：1点/2点到了右下角（是同时到的）

• 算法实现（Java）

public static void printMatrixZigZag(int[][] matrix) {
int tR = 0;
int tC = 0;
int dR = 0;
int dC = 0;
int endR = matrix.length - 1;
int endC = matrix[0].length - 1;
boolean fromUp = false;
while (tR != endR + 1) {
printLevel(matrix, tR, tC, dR, dC, fromUp);
tR = tC == endC ? tR + 1 : tR;
tC = tC == endC ? tC : tC + 1;
dC = dR == endR ? dC + 1 : dC;
dR = dR == endR ? dR : dR + 1;
fromUp = !fromUp;
}
System.out.println();
}public static void printLevel(int[][] m, int tR, int tC, int dR, int dC,
boolean f) {
if (f) {
while (tR != dR + 1) {
System.out.print(m[tR++][tC--] + " ");
}
} else {
while (dR != tR - 1) {
System.out.print(m[dR--][dC++] + " ");
}
}
}

题目八：在行列都排好序的矩阵中查找

• 题目表述

  • 给定一个N* M的整型矩阵matrix和一个整数K，matrix的每一行和每一列都是有序的。实现一个函数，判断K是否在matrix中；要求时间复杂度O(n+m)，空间复杂度O(1)

    例如：

    0 1 2 5

    2 3 4 7

    4 4 4 8

    5 7 7 9

    如果K=7，则返回true；若K=6，则返回false；

• 思路：

  • 很容易看出是找到一个初始值然后与K进行比较，小/大都往不同的方向继续走
  • 选择初始值一般为左下点或者右上点，因为跟他们比较之后继续走的方向唯一。

• 算法实现（Java）

public static boolean isContains(int[][] matrix, int K) {
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col > -1) {
if (matrix[row][col] == K) {
return true;
} else if (matrix[row][col] > K) {
col--;
} else {
row++;
}
}
return false;
}

题目九：打印两个有序链表的公共部分（水题）

• 题目表述：

  • 给定两个有序链表的的头指针head1和head2，打印两个有序链表的公共部分

• 思路

  • 谁小谁往后走，相等打印再一起走一步

题目十：判断一个链表是否是回文结构

• 题目表述：

  • 给定一个链表的头节点，请判断该链表是否是回文结构，要求时间复杂度O(n)

• 思路一：额外空间O(n)

  • 利用栈结构，全部遍历一遍链表入栈
  • 再遍历一遍链表，比对栈顶元素与遍历元素是否相等，相等出栈继续下一个元素直至最后

• 思路二：额外空间O(n/2)

  • 利用快慢两个指针，慢指针步长1，快指针步长2（Trick经常用）
  • 当快指针越界时，慢指针刚好到链表的中点（如何找到链表的中点）
  • 再将慢指针后续压栈，再逐一弹栈与头节点一起遍历比对元素是否相等

• 思路三：额外空间O(1)

  • 与思路二相同，慢指针刚好到链表中点处
  • 将慢指针后续链表逆序，覆盖原来的后半空间；半链表逆序，两头链表往中间指向，中间结点指向null，慢指针指向后半链表的表头
  • 再将慢指针与头节点遍历逐一比对元素是否相等

• 算法实现（Java）

//思路一代码：
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<Node>();
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;
}//思路二代码：
public static boolean isPalindrome2(Node head) {
if (head == null || head.next == null) {
return true;
}
Node right = head.next;
Node cur = head;
while (cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
Stack<Node> stack = new Stack<Node>();
while (right != null) {
stack.push(right);
right = right.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 n3 = null;
while (n2 != null) { // right part convert 链表逆序操作
n3 = n2.next; // n3 -> save next node
n2.next = n1; // next of right node convert
n1 = n2; // n1 move
n2 = n3; // n2 move
}
n3 = n1; // n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) { // check palindrome
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
n1 = n3.next;
n3.next = null;
while (n1 != null) { // recover list
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}

题目十一：单向链表按照某值划分小等大形式

• 题目表述：给定一个链表头节点head，节点值是整型，再给定一个整数pivot。实现一个调整列表的功能，使链表左边小于pivot，再是等于pivot，右边大于pivot的结点；各区域内部要求相对次序不变

  • 例如：9-0-4-5-1，pivot=3；
  • 调整后是：0-1-9-4-5

• 思想：

  • 看到某值分区域 – 想到就是 partation – 该题就是一个partation的链表版本

• 思路一：额外空间O(n)

  • 将链表的值存入一个数组里面，在数组里面进行partation – 数组随机访问时间复杂度O(1)
  • partation完之后再返回拼接链表

• 思路二：额外空间O(1)

  • 设三个头节点small，big，equal，第一次遍历链表，找到第一次出现的三个区域元素 – 作为头节点
  • 第二次遍历链表，原节点跳过（通过内存地址 == 判断），后续节点属于哪个区域就连接到那个区域后面
  • 最后再把三个链表组合即可

• 算法实现（Java）

public static class Node {
public int value;
public Node next;public Node(int data) {
this.value = data;
}
}//思路一
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[] nodeArr = new Node[i];
i = 0;
cur = head;
for (i = 0; i != nodeArr.length; i++) {     // 数组赋值
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr, pivot);
for (i = 1; i != nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}public static void arrPartition(Node[] nodeArr, int pivot) {    // partation过程
int small = -1;
int big = nodeArr.length;
int index = 0;
while (index != big) {
if (nodeArr[index].value < pivot) {
swap(nodeArr, ++small, index++);
} else if (nodeArr[index].value == pivot) {
index++;
} else {
swap(nodeArr, --big, index);
}
}
}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
// every node distributed to three lists
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
} else if (head.value == pivot) {
if (eH == null) {
eH = head;
eT = head;
} else {
eT.next = head;
eT = head;
}
} else {
if (bH == null) {
bH = head;
bT = head;
} else {
bT.next = head;
bT = head;
}
}
head = next;
}
// small and equal reconnect
if (sT != null) {
sT.next = eH;
eT = eT == null ? sT : eT;
}
// all reconnect
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 class Node {
public int value;
public Node next;
public Node rand;public Node(int data) {
this.value = data;
}
}

• 思路一：

  • 最好的方法就是用哈希表做映射关系
  • 首先 Node new1=new Node(node1.value) 将所有的值先进行生成
  • 再构造哈希表 map(old_node,new_node)，做节点映射
  • 之后遍历原链表，构造new节点的next与rand指针节点 –

    new.next=map.get(old.next)

    new.rand=map.get(old.rand)

• 思路二：

  • 如果不允许用哈希表，就需要用另外一种构造对应关系的方法
  • 将新节点插入原节点next中间：old->new->old.next
  • 之后遍历链表，一次性拿出old与new两个节点：令

    new.rand=old.rand.next

    new.next=new.next.next

• 算法实现（Java）

//思路一
public static Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.value));
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 null;
}
Node cur = head;
Node next = null;
// copy node and link to every node     //每个后面都new一个新节点
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
// set copy node rand
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand != null ? cur.rand.next : null;
cur = next;
}
Node res = head.next;
cur = head;
// split
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
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();
}

题目十三：两个单向链表相交的一系列问题 （重要）

• 题目表述：单向链表可能有环也可能无环。给定两个链表head1和head2，这两个链表可能相交也可能不相交。请实现一个函数，若相交则返回相交第一个节点；若不相交，则返回Null。

  要求：如果head1长度为N，head2长度为M，时间复杂度达到O(N+M)，空间复杂度O(1).

• 首先得判断单向链表是否有环

子问题：单向链表如何判断有无环

• 如果有链表有环，返回第一个入环节点；否则返回Null

• 思路一：

  • 利用哈希表：凡是跟next节点指向本链表节点的题都要想到哈希表

  • 遍历链表，每个节点放到哈希表里，如果map.get(node)没有值，则无环；否则有环，有值处就是第一个入环节点

• 思路二：

  • 不用哈希表：快F慢S指针，如果无环，则快指针一定会走到Null；如果有环，则快指针F一定会遇上慢指针S。相遇之后，快指针F回到开头，变成慢指针（即每次走一步）；然后两个慢指针会在入环节点处相遇! – （图论数学结论）

设计思路

• getLoopNode返回单向链表环路第一个节点

• getIntersectNode返回相交第一个节点

• 情况①：head1&head2都无环路 – noLoop

  • 因为单向链表，链表只有一个分支next，所有无环路只可能两种情况：|| & Y

  • 利用哈希表：将head1加入哈希表，head2进行map.get，如果有值则该值就是相交点。

  • 不用哈希表：先遍历一遍，得到head1与head2长度，比较最后节点的地址，若相同则有交点，否则无； – 之后比较head1&head2长度，长的先走多余那段，之后两者同时前进，必然会在第一个交点处相遇

• 情况②：一个链表有环另一个无环 – 不可能出现相交

  • 6 1 – 链表形状如此，1在6任何位置处都会使得1是有环链表，故无相交可能性

• 情况③：都是有环链表 – bothLoop

  • 66 & 环前相交 & 环环相交

  • 环前相交：即 loop1==loop2，此时以 loop环节点作为最后节点，进行调用noLoop即可。

  • 环环相交：loop1 != loop2，则可能无相交&环环相交，此时让Loop1往后遍历，如果没有遇到Loop2回到原点Loop1，则是66 ；若是遇到Loop2，则是环环相交，Loop1Loop2都可作为相交点（因为是环相交）

• 算法实现（Java）

public static class Node {
public int value;
public Node next;public Node(int data) {
this.value = data;
}
}public static Node getIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}public static Node getLoopNode(Node head) {// 得到环链表第一个入环节点
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node n1 = head.next; // n1 -> slow
Node n2 = head.next.next; // n2 -> fast
while (n1 != n2) {
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // n2 -> walk again from head
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1.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);}}

题目十四：反转单向&双向链表

• 分别实现反转单向链表双向链表函数，时间复杂度O(N)，空间复杂度O(1)

  • 反转单向链表：两两节点，将next指向方向反向即可

  • 反转双向链表：两两节点，将next、pre指向方向反向即可

• 算法实现（Java）

public static class Node {
public int value;
public Node next;public Node(int data) {
this.value = data;
}
}public static Node reverseList(Node 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));}