算法与数据结构08：链表问题
快慢指针
四个类似的问题：
1、输入链表头部，奇数长度返回中点，偶数长度返回上中点
2、输入链表头部，奇数长度返回中点，偶数长度返回下中点
3、输入链表头部，奇数长度返回中点前一个，偶数长度返回上中点前一个
4、输入链表头部，奇数长度返回中点前一个，偶数长度返回下中点前一个
处理逻辑都一样，都是设置一个快指针和一个慢指针，快指针每次遍历两个结点，慢指针每次遍历一个结点，当快指针无法往后遍历时，返回慢指针指向的节点。
唯一不同的就是慢指针和快指针的初始指向。
/**
* 快慢指针
*/
public class LinkedList01 {
/**
* 输入链表头部，奇数长度返回中点，偶数长度返回上中点
* @param head
* @return
*/
public static Node find01(Node head) {
if (head == null || head.next == null) {
return head;
}
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
/**
* 输入链表头部，奇数长度返回中点，偶数长度返回下中点
* @param head
* @return
*/
public static Node find02(Node head) {
if (head == null || head.next == null) {
return head;
}
Node slow = head.next;
Node fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
/**
* 输入链表头部，奇数长度返回中点前一个，偶数长度返回上中点前一个
* @param head
* @return
*/
public static Node find03(Node head) {
if (head == null || head.next == null) {
return head;
}
Node slow = head;
Node fast = head.next.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
/**
* 输入链表头部，奇数长度返回中点前一个，偶数长度返回下中点前一个
* @param head
* @return
*/
public static Node find04(Node head) {
if (head == null || head.next == null) {
return head;
}
Node slow = head;
Node fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private static class Node {
private Node next;
private int value;
}
}
输入一个链表头结点，判断链表是否是回文结构
三种方法：
1、把链表结点压入栈中，此时栈中结点的顺序与链表相反，一个个弹出与链表结点比较即可
2、通过快慢指针，然慢指针指向链表中间节点，然后只把后半部分节点压入栈中，与列表节点进行比较，节省一半空间
3、通过快慢指针，然慢指针指向链表中间节点，然后把后把部分的节点的next指针反转，再用两个指针，一头一尾，遍历进行比较，比较完毕后还原后半部分节点的next指针
第三种方法：
1、先通过快慢（块指针每次走两步，慢指针每次走一步）指针，找到中点
2、把慢指针后面的点的指针逆序
3、左右指针遍历，左右点比对，指针某个指针遍历到null为止
4、遍历完毕后，还原链表
/**
* 输入一个链表头结点，判断链表是否是回文结构
*/
public class LinkedList02 {
public static boolean isReverse01(Node head) {
if (head == null && head.next == null) return true;
Stack<Node> stack = new Stack<>();
Node help = head;
//把链表中的所有结点压入栈中
while (help != null) stack.push(help);
boolean res = true;
help = head;
//此时从栈顶到栈底，结点顺序与链表相反，从链表头部开始遍历，每遍历一个节点，从栈中弹出一个进行比较
while (!stack.isEmpty()) {
res &= stack.pop().value == help.value;
help = help.next;
}
return res;
}
public static boolean isReverse02(Node head) {
if (head == null && head.next == null) return true;
//使用快慢指针，取到链表中点，只把链表后半部分压入栈中，与前半部分比较
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
//把链表后半部分压入栈中
Stack<Node> stack = new Stack<>();
Node n2 = slow.next;
boolean res = true;
while (n2 != null) {
stack.push(n2);
n2 = n2.next;
}
//与前半部分比较
n2 = head;
while (!stack.isEmpty()) {
res &= stack.pop().value == n2.value;
n2 = n2.next;
}
return res;
}
public static boolean isReverse03(Node head) {
if (head == null && head.next == null) return true;
//使用快慢指针，取到链表中点，把链表后半部分指针反转，然后与前半部分进行比较，笔记完毕后把指针还原
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
//把链表后半部分指针反转
Node n1 = slow;
Node n2 = n1.next;
n1.next = null;
Node n3 = null;
while (n2 != null) {
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
//前后两半部分进行比较
n3 = n1;
n2 = head;
boolean res = true;
while (n1 != null && n2 != null) {
res &= n1.value == n2.value;
n1 = n1.next;
n2 = n2.next;
}
//链表还原
n1 = n3.next;
n3.next = null;
while (n1 != null) {
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
private static class Node {
private Node next;
private int value;
}
}
将单向链表按某值划分为左边小，中间等于，右边大于的形式
两种方法：
1、把链表的每个节点放到数组里，做一次partition（笔试用）
2、弄6个指针代表3个链表，分别是小于区域头指针、大于区域尾指针、等于区域头指针、等与区域尾指针、大于区域头指针、大于区域尾指针，遍历原链表，生成3个新链表，最后把这3个链表连起来，就是新的符合要求的链表（面试用）
第二种方法：
1、遍历链表，往3个区域发货
2、遍历完后就是3个新链表
3、链好3个新链表，返回新的头结点
/**
* 将单向链表按某值划分为左边小，中间等于，右边大于的形式
*/
public class LinkedList03 {
public static Node partition01(Node head, int pivot) {
if (head == null || head.next == null) return head;
//计算链表大小，并创建对应大小的数组，临时存放链表结点
Node help = head;
int size = 0;
while (help != null) {
size++;
head = help.next;
}
Node[] arr = new Node[size];
help = help;
int index = 0;
while (help != null) {
arr[index++] = help;
help = help.next;
}
//根据pivot基准值，对数组做partition操作
int i1 = -1; //(...i1] 小于区
int i2 = 0; // (i1...i2] 等于区
int i3 = arr.length; // (i2...i3]大于区
while (i2 != i3) {
Node curr = arr[i2];
if (curr.value < pivot) {
swap(arr, ++i1, i2++);
} else if (curr.value > pivot) {
swap(arr, i2, --i3);
} else {
i2++;
}
}
//遍历数组，把结点串起来
Node prev = arr[0];
for (int i = 1; i < arr.length; i++) {
prev.next = arr[i];
prev = arr[i];
}
return arr[0];
}
public static Node partition02(Node head, int pivot) {
if (head == null || head.next == null) return head;
Node smallHead = null; //小于区头结点
Node smallTail = null; //小于区尾结点
Node equalsHead = null; //等于区头结点
Node equalsTail = null; //等于区尾结点
Node bigHead = null; //大于区头结点
Node bigTail = null; //大于区尾结点
//遍历链表，组装小于区、等于区、大于区的链表，并且每遍历一个结点，就把原来的next指针断掉
Node next;
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (smallHead == null) {
smallHead = head;
smallTail = head;
} else {
smallTail.next = head;
smallTail = head;
}
} else if (head.value == pivot) {
if (equalsHead == null) {
equalsHead = head;
equalsTail = head;
} else {
equalsTail.next = head;
equalsTail = head;
}
} else {
if (bigHead == null) {
bigHead = head;
bigTail = head;
} else {
bigTail.next = head;
bigTail = head;
}
}
head = next;
}
//小于区的尾部连接等于区的头部，等于区的头部连接大于区的头部，但是要判断边界情况，就是小于区、等于区有可能为空
if (smallHead != null) {
smallTail.next = equalsHead;
equalsTail = equalsHead == null ? smallTail : equalsTail;
}
if (equalsHead != null) {
equalsTail = bigHead;
}
return smallHead != null ? smallHead : (equalsHead != null ? equalsHead : bigHead);
}
private static class Node {
private int value;
private Node next;
}
private static void swap(Node[] arr, int i, int j) {
Node temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
链表结点带rand指针克隆问题
两种方法：
1、遍历原链表，生成一个map，key是原链表节点，value是新的克隆结点，然后遍历map，处理每个克隆节点的next指针，和rand指针，两指针要连的节点，都可以通过原链表节点在map中找到（笔试用）
2、遍历链表，生成克隆结点，生成克隆结点后，原链表节点的next指针指向克隆结点，然后克隆结点的next指针指向原链表节点的下一个节点，也就是克隆结点嵌在原链表中间；然后成对遍历链表，处理克隆结点的rand指针；然后在遍历一次链表，分离两个链表
第二种方法：
1、假设这是原链表
2、生成克隆结点，嵌在原链表中间
3、成对遍历链表，处理克隆结点的rand指针
4、分离出克隆结点链表
/**
* 链表结点带rand指针克隆问题
*/
public class LinkedList04 {
public static Node clone01(Node head) {
if (head == null) return null;
//原结点 -> 克隆结点
Map<Node, Node> map = new HashMap<>();
//建立原结点与克隆结点的映射关系
Node help = head;
while (help != null) {
Node copy = new Node();
copy.value = help.value;
map.put(help, copy);
help = help.next;
}
//根据map中记录的原结点与克隆结点的映射关系，给克隆结点的next指针与rand指针赋值
help = head;
while (help != null) {
Node copy = map.get(help);
if (help.next != null) copy.next = map.get(help.next);
if (help.rand != null) copy.rand = map.get(help.rand);
help = help.next;
}
return map.get(head);
}
public static Node clone02(Node head) {
//1、遍历列表，克隆结点，并把克隆结点连接到原结点后面
//1->1`->2->2`->3->3`
Node help = head;
while (help != null) {
Node next = help.next;
Node copy = new Node();
copy.value = help.value;
help.next = copy;
copy.next = next;
help = next;
}
//2、遍历链表，处理克隆结点的rand指针
help = head;
while (help != null) {
Node next = help.next.next;
Node copy = help.next;
if (help.rand != null) copy.rand = help.rand.next;
help = next;
}
//3、链表分离
Node res = help.next;
help = head;
while (help != null) {
Node next = help.next.next;
Node copy = help.next;
help.next = next;
if (next != null) copy.next = next.next;
help = next;
}
return res;
}
private static class Node{
private int value;
private Node next;
private Node rand;
}
}
给定一个链表，如果有环则返回环中的第一个节点，没有则返回null
定一个快指针和一个慢指针，快指针一次走两步，慢指针一次走一步，两指针在环中相遇后，快指针回到头节点，两指针都每次走一步，它们必在入环节点相遇
/**
* 给定一个链表，如果有环则返回环中的第一个节点，没有则返回null
*/
public class LinkedList05 {
public static Node find(Node head) {
if (head == null || head.next == null || head.next.next == null) return null;
//快慢指针，如果有环，两指针会在环中相遇
Node slow = head.next;
Node fast = head.next.next;
while (slow != fast) {
if (fast == null || fast.next == null) return null;
slow = slow.next;
fast = fast.next.next;
}
//让fast指针回到头结点，每一次走一步，快慢指针相遇的结点，就是环中第一个节点
fast = head;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
private static class Node {
private int value;
private Node next;
}
}
给定两个无环链表，返回两个链表相交的第一个节点，没有则返回null
1、先遍历两个链表，并记录长度
2、看两链表尾节点是否相等，是则代表有相交节点，否则两链表不相交
3、如果相交，长链表指针先走差值步，然后链表指针每次走一步，最后必在相交节点相遇
/**
* 给定两个无环链表，返回两个链表相交的第一个节点，没有则返回null
*/
public class LinkedList06 {
public static Node findIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) return null;
//先遍历head1，计算head1长度
int len = 0;
Node curr1 = head1;
while (curr1.next != null) {
len++;
curr1 = curr1.next;
}
//遍历head2，每遍历一个结点，len减一，计算出两个链表长度的差值
Node curr2 = head2;
while (curr2.next != null) {
len--;
curr2 = curr2.next;
}
//此时curr1和curr2都指向各自链表的尾结点，如果不是同一个尾结点，代表两链表没有相交，返回null
if (curr1 != curr2) return null;
//调整curr1和curr2指针，让cuur1指针指向长度较长的链表头结点
curr1 = len < 0 ? head2 : head1;
curr2 = curr1 == head1 ? head2 : head1;
//此时len为两链表长度的差值，保证len为正数
len = Math.abs(len);
//curr1先走len步，使得curr1和curr2指向的结点开始到尾节点长度一样
while (len != 0) {
len--;
curr1 = curr1.next;
}
//curr1和curr2每次各自走一步，最后必会到达相交处
while (curr1 != curr2) {
curr1 = curr1.next;
curr2 = curr2.next;
}
return curr1;
}
private static class Node {
private int value;
private Node next;
}
}
两个有环链表，给定链表头结点和环中第一个节点，找出两个链表相交的结点，没有相交则返回null
/**
* 两个有环链表，给定链表头结点和环中第一个节点，找出两个链表相交的结点，没有相交则返回null
*/
public class LinkedList07 {
public static Node findLoopIntersect(Node head1, Node loop1, Node head2, Node loop2) {
Node curr1 = null;
Node curr2 = null;
// 第一种情况：两个链表在环外相交
if (loop1 == loop2) {
curr1 = head1;
curr2 = head2;
//遍历链表1，计算到入环结点的长度
int len = 0;
while (curr1 != loop1) {
len++;
curr1 = curr1.next;
}
//遍历链表二，也是到入环结点就停止，计算两个链表长度的差值
while (curr2 != loop2) {
len--;
curr2 = curr2.next;
}
//调整curr1指向长度较长链表的头结点
curr1 = len < 0 ? head2 : head1;
curr2 = curr1 == head1 ? head2 : head1;
//保证len为正数
len = Math.abs(len);
//curr1走len步，此时cuur1到入环结点与curr2到入环结点的长度相同
while (len > 0) {
len--;
curr1 = curr1.next;
}
//curr1和curr2每次走1步，到入环结点或入环结点前必会相遇
while (curr1 != curr2) {
curr1 = curr1.next;
curr2 = curr2.next;
}
return curr1;
} else {
//第二种情况，两个链表的入环结点不相同
curr1 = loop1.next;
//从loop1开始遍历链表1，看是否会与loop2相遇，是则两链表相交，返回loop1或loop2都可以，不会相遇则会回到loop1，返回null
while (curr1 != loop1) {
if (curr1 == loop2) return loop1;
curr1 = curr1.next;
}
return null;
}
}
private static class Node {
private int value;
private Node next;
}
}
给定两个链表，有可能有环，也有可能无环，返回两个链表的相交结点，没有相交则返回null
可能的情况：
1、两个链表都无环，退化为寻找两个无环链表相交结点的问题
2、一个链表有环，一个链表无环，不可能相交
3、两个链表都有环，分三种情况：
3.1、两个有环链表，不相交
3.2、两个有环链表，在环外相交（包括入环节点）
3.3、两个有环链表，在环内相交（相交但是入环节点不同）
解法：
1、先分别通过链表寻找入环节点的方法，找到两个链表的入环节点
2、如果两个入环节点都是null，则符号情况1，用寻找两个无环链表相交结点的方法求解
3、如果一个入环节点为null，另一个不为null，则符号情况2，返回null
4、如果两个入环节点都不为null，如果两个入环节点相等，则是情况3.2，以入环节点为终点，利用两无环链表寻找相交点的方式求交点
5、如果两个入环节点都不为null，以其中一个入环节点为目标节点，另一个入环节点为起点，转一圈，看是否能到达目标节点，如果回到起点都没遇到目标节点，则是情况3.1，返回null；如果遇到了，返回两个入环节点的其中一个就行。
/**
* 给定两个链表，有可能有环，也有可能无环，返回两个链表的相交结点，没有相交则返回null
*/
public class LinkedList08 {
public static Node find(Node head1, Node head2) {
if (head1 == null || head2 == null) return null;
//1、找出两个链表的入环结点
Node loop1 = findLoopNode(head1);
Node loop2 = findLoopNode(head2);
//如果loop1和loop2都为null，则退化为寻找两个无环链表相交结点的问题
if (loop1 == null && loop2 == null) {
return findIntersectNodeNoLoop(head1, head2);
}
//如果loop1和loop2都不为空，则简化为寻找两个有环链表的相交结点问题
if (loop1 != null && loop2 != null) {
return findLoopIntersect(head1, loop1, head2, loop2);
}
//如果一个链表有环，一个链表无环，不可能相交，返回null
return null;
}
/**
* 找出两个有环链表的相交结点，没有则返回null
* @param head1
* @param loop1
* @param head2
* @param loop2
* @return
*/
public static Node findLoopIntersect(Node head1, Node loop1, Node head2, Node loop2) {
Node curr1 = null;
Node curr2 = null;
// 第一种情况：两个链表在环外相交
if (loop1 == loop2) {
curr1 = head1;
curr2 = head2;
//遍历链表1，计算到入环结点的长度
int len = 0;
while (curr1 != loop1) {
len++;
curr1 = curr1.next;
}
//遍历链表二，也是到入环结点就停止，计算两个链表长度的差值
while (curr2 != loop2) {
len--;
curr2 = curr2.next;
}
//调整curr1指向长度较长链表的头结点
curr1 = len < 0 ? head2 : head1;
curr2 = curr1 == head1 ? head2 : head1;
//保证len为正数
len = Math.abs(len);
//curr1走len步，此时cuur1到入环结点与curr2到入环结点的长度相同
while (len > 0) {
len--;
curr1 = curr1.next;
}
//curr1和curr2每次走1步，到入环结点或入环结点前必会相遇
while (curr1 != curr2) {
curr1 = curr1.next;
curr2 = curr2.next;
}
return curr1;
} else {
//第二种情况，两个链表的入环结点不相同
curr1 = loop1.next;
//从loop1开始遍历链表1，看是否会与loop2相遇，是则两链表相交，返回loop1或loop2都可以，不会相遇则会回到loop1，返回null
while (curr1 != loop1) {
if (curr1 == loop2) return loop1;
curr1 = curr1.next;
}
//第三种情况，两链表不相交
return null;
}
}
/**
* 找出两个无环链表的相交几点，没有则返回null
* @param head1
* @param head2
* @return
*/
public static Node findIntersectNodeNoLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) return null;
//先遍历head1，计算head1长度
int len = 0;
Node curr1 = head1;
while (curr1.next != null) {
len++;
curr1 = curr1.next;
}
//遍历head2，每遍历一个结点，len减一，计算出两个链表长度的差值
Node curr2 = head2;
while (curr2.next != null) {
len--;
curr2 = curr2.next;
}
//此时curr1和curr2都指向各自链表的尾结点，如果不是同一个尾结点，代表两链表没有相交，返回null
if (curr1 != curr2) return null;
//调整curr1和curr2指针，让cuur1指针指向长度较长的链表头结点
curr1 = len < 0 ? head2 : head1;
curr2 = curr1 == head1 ? head2 : head1;
//此时len为两链表长度的差值，保证len为正数
len = Math.abs(len);
//curr1先走len步，使得curr1和curr2指向的结点开始到尾节点长度一样
while (len != 0) {
len--;
curr1 = curr1.next;
}
//curr1和curr2每次各自走一步，最后必会到达相交处
while (curr1 != curr2) {
curr1 = curr1.next;
curr2 = curr2.next;
}
return curr1;
}
/**
* 找出链表入环结点，无环则返回null
* @param head
* @return
*/
public static Node findLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) return null;
//快慢指针，如果有环，两指针会在环中相遇
Node slow = head.next;
Node fast = head.next.next;
while (slow != fast) {
if (fast == null || fast.next == null) return null;
slow = slow.next;
fast = fast.next.next;
}
//让fast指针回到头结点，每一次走一步，快慢指针相遇的结点，就是环中第一个节点
fast = head;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
private static class Node {
private int value;
private Node next;
}
}
补充-LUR算法
简单版-直接使用系统提供的api
class LRUCache extends LinkedHashMap {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return (int)super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
}
纯手写版：
/**
* LRU内存替换算法
* Created by huangjunyi on 2022/10/1.
*/
public class _01LRU {
private static class Node<K, V> {
private Node last;
private Node next;
private K key;
private V value;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
private static class DoubleLinkedList<K, V> {
private Node<K, V> head;
private Node<K, V> tail;
public DoubleLinkedList() {
this.head = null;
this.tail = null;
}
public void add (Node<K, V> node) {
if (node == null) return;
if (head == null) head = tail = node;
else {
node.last = tail;
tail.next = node;
tail = node;
}
}
public void moveToTail(Node<K, V> node) {
if (node == tail) return;
else if (node == head) {
head = node.next;
head.last = null;
} else {
node.last.next = node.next;
node.next.last = node.last;
}
node.last = tail;
node.next = null;
tail.next = node;
tail = node;
}
public Node<K, V> removeCurrHead() {
if (head == null) return null;
Node res = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = res.next;
res.next = null;
head.last = null;
}
return res;
}
}
private static class LRUCache<K, V> {
private HashMap<K, Node<K, V>> keyNodeMap;
private DoubleLinkedList<K, V> list;
private int capacity;
public LRUCache(int capacity) {
keyNodeMap = new HashMap<>();
list = new DoubleLinkedList<>();
this.capacity = capacity;
}
public void put(K key, V value) {
if (keyNodeMap.containsKey(key)) {
Node<K, V> node = keyNodeMap.get(key);
node.value = value;
list.moveToTail(node);
} else {
if (keyNodeMap.size() == capacity) {
Node<K, V> node = list.removeCurrHead();
if (node != null) keyNodeMap.remove(node.key);
Node<K, V> newNode = new Node<>(key, value);
keyNodeMap.put(key, newNode);
list.add(newNode);
}
}
}
}
}
本文含有隐藏内容，请 开通VIP 后查看