首页 计算机科学 算法与数据结构

# 链表

# 哈希表的简单介绍

  1. 哈希表在使用层面上可以理解为一种集合结构。
  2. 如果只有 key，没有伴随数据 value，可以使用 HashSet 结构 (C++ 中叫 UnOrderedSet)。
  3. 如果既有 key，又有伴随数据 value，可以使用 HashMap 结构 (C++ 中叫 UnOrderedMap)。
  4. 有无伴随数据，是 HashMap 和 HashSet 唯一的区别，底层的实际结构是一回事。
  5. 使用哈希表 (put)、删 (remove)、改 (put)、查 (get) 的操作，可以认为时间复杂度为 O (1)，但是常数时间比较大。
  6. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小。
  7. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小 (8bit)。
Node.java
import java.util.Objects;
/**
 * @Author: LightRain
 * @Description: 链表节点
 * @DateTime: 2023-05-09 21:38
 * @Version：1.0
 **/
public class Node {
    private int data;
    private Node next;
    public Node() {
    }
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    public Node(int i) {
        this.data = i;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Node node = (Node) o;
        return data == node.data && Objects.equals(next, node.next);
    }
    @Override
    public int hashCode() {
        return Objects.hash(data, next);
    }
}
HashSetAndHashMap.java
import java.util.HashMap;
import java.util.HashSet;
/**
 * @Author: LightRain
 * @Description: HashSet 和 HashMap 的使用
 * 哈希表在使用的时候都是常数级别的时间复杂度
 * 和数据量没有关系，数据量再大也可以做到常数
 * 级别的返回值
 * 时间复杂度：O (logN)
 * @DateTime: 2023-05-09 21:37
 * @Version：1.0
 **/
public class HashSetAndHashMap {
    public static void main(String[] args) {
        Node nodeA = null;
        Node nodeB = null;
        Node nodeC = null;
        HashSet<Integer> hashSet1 = new HashSet<>();
        hashSet1.add(3);
        System.out.println("hashSet1.contains(3) = " + hashSet1.contains(3));
        hashSet1.remove(3);
        System.out.println("hashSet1.contains(3) = " + hashSet1.contains(3));
        System.out.println("================================================");
        HashMap<Integer, String> hashMap = new HashMap<>();
        hashMap.put(1, "zuo");
        hashMap.put(1, "cheng");
        hashMap.put(2, "2");
        System.out.println("hashMap.containsKey(1) = " + hashMap.containsKey(1));
        System.out.println("hashMap.get(1) = " + hashMap.get(1));
        System.out.println("hashMap.get(4) = " + hashMap.get(4));
        hashMap.remove(2);
        System.out.println("hashMap.get(2) = " + hashMap.get(2));
        System.out.println("================================================");
        //HashSet2 的 key 是非基础类型 ->Node 类型
        nodeA = new Node(1);
        nodeB = new Node(1);
        HashSet<Node> hashSet2 = new HashSet<>();
        hashSet2.add(nodeA);
        System.out.println("hashSet2.contains(nodeA) = " + hashSet2.contains(nodeA));
        System.out.println("hashSet2.contains(nodeB) = " + hashSet2.contains(nodeB));
        hashSet2.remove(nodeA);
        System.out.println("hashSet2.contains(nodeA) = " + hashSet2.contains(nodeA));
        System.out.println("================================================");
        //HashMap1 的 key 是基础类型 ->String 类型
        HashMap<String, Integer> hashMap1 = new HashMap<>();
        String str1 = "key";
        String str2 = "key";
        hashMap1.put(str1, 1);
        System.out.println("hashMap1.containsKey(str1) = " + hashMap1.containsKey(str1));
        System.out.println("hashMap1.containsKey(str2) = " + hashMap1.containsKey(str2));
        System.out.println("hashMap1.get(str1) = " + hashMap1.get(str1));
        System.out.println("hashMap1.get(str2) = " + hashMap1.get(str2));
        hashMap1.put(str2, 2);
        System.out.println("hashMap1.containsKey(str1) = " + hashMap1.containsKey(str1));
        System.out.println("hashMap1.containsKey(str2) = " + hashMap1.containsKey(str2));
        System.out.println("hashMap1.get(str1) = " + hashMap1.get(str1));
        System.out.println("hashMap1.get(str2) = " + hashMap1.get(str2));
        hashMap1.remove(str1);
        System.out.println("hashMap1.containsKey(str1) = " + hashMap1.containsKey(str1));
        System.out.println("hashMap1.containsKey(str2) = " + hashMap1.containsKey(str2));
        System.out.println("================================================");
    }
}
# 有序表的简单介绍
  1. 有序表在使用层面上可以理解为一种集合结构。
  2. 如果只有 key，没有伴随数据 value，可以使用 TreeSet 结构 (C++ 中叫 OrderedSet)。
  3. 如果既有 key，又有伴随数据 value，可以使用 TreeMap 结构 (C++ 中叫 OrderedMap)。
  4. 有无伴随数据，是 TreeSet 和 TreeMap 唯一的区别，底层的实际结构是一回事。
  5. 有序表和哈希表的区别是，有序表把 key 按照顺序组织起来，而哈希表完全不组织。
  6. 红黑树、AVL 数、size-balance-tree 和跳表等都属于有序表结构，只是底层具体实现不同。
  7. 放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小。
  8. 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小。
  9. 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度 O (logN) 级别。
# 有序表的固定操作
  1. void put (K key,V value): 将一个 (key,value) 记录加入到表中，或者将 key 的记录更新成 value。
  2. V get (K key): 根据给定的 key，查询 value 并返回。
  3. void remove (K key): 移除 key 的记录。
  4. boolean containsKey (K key): 询问是否有关于 key 的记录。
  5. K firstKey (): 返回所有键值的排序结果中，最左 (最小) 的那个。
  6. K lastKey (): 返回所有键值的排序结果中，最右 (最大) 的那个。
  7. K floorKey (K key): 如果表中存入过 key，返回 key: 否则返回所有键值的排序结果中，key 的前一个。
  8. K ceilingKey (K key): 如果表中存入过 key，返回 key: 否则返回所有键值的排序结果中，key 的后一个。
  9. 以上所有操作时间复杂度都是 O (logN),N 为有序表含有的记录数。
import java.util.Comparator;
import java.util.Objects;
/**
 * @Author: LightRain
 * @Description: 链表节点
 * @DateTime: 2023-05-09 21:38
 * @Version：1.0
 **/
public class Node {
    private int data;
    private Node next;
    public Node() {
    }
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    public Node(int i) {
        this.data = i;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Node node = (Node) o;
        return data == node.data && Objects.equals(next, node.next);
    }
    @Override
    public int hashCode() {
        return Objects.hash(data, next);
    }
    /**
     * 自定义比较器
     */
    public static class NodeComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.data - o2.data;
        }
    }
}
TreeSetAndTreeMap.java
import java.util.TreeMap;
import java.util.TreeSet;
/**
 * @Author: LightRain
 * @Description: TreeSet 和 TreeMap
 * 有序表在使用的时候都是常数级别的时间复杂度
 * 和数据量没有关系，数据量再大也可以做到常数
 * 级别的返回值
 * 时间复杂度：O (logN)
 * @DateTime: 2023-05-09 22:28
 * @Version：1.0
 **/
public class TreeSetAndTreeMap {
    public static void main(String[] args) {
        Node nodeA = null;
        Node nodeB = null;
        Node nodeC = null;
        nodeA = new Node(5);
        nodeB = new Node(3);
        nodeC = new Node(7);
        // 红黑树
        TreeSet<Node> treeSet = new TreeSet<>();
        // 以下代码会报错，因为没有提供 Node 类型的比较器
        try {
            treeSet.add(nodeA);
            treeSet.add(nodeB);
            treeSet.add(nodeC);
        } catch (Exception e) {
            System.out.println("错误信息：" + e.getMessage());
        }
        System.out.println("================================================");
        // 添加比较器才可添加节点成功
        treeSet = new TreeSet<>(new Node.NodeComparator());
        try {
            treeSet.add(nodeA);
            treeSet.add(nodeB);
            treeSet.add(nodeC);
            System.out.println("节点添加成功");
        } catch (Exception e) {
            System.out.println("错误信息：" + e.getMessage());
        }
        System.out.println("================================================");
        // 展示有序表常用操作
        TreeMap<Integer, String> treeMap1 = new TreeMap<>();
        treeMap1.put(7, "我是7");
        treeMap1.put(5, "我是5");
        treeMap1.put(4, "我是4");
        treeMap1.put(3, "我是3");
        treeMap1.put(9, "我是9");
        treeMap1.put(2, "我是2");
        System.out.println(treeMap1.containsKey(5));
        System.out.println(treeMap1.get(5));
        System.out.println(treeMap1.firstKey() + ",我最小");
        System.out.println(treeMap1.lastKey() + ",我最大");
        System.out.println(treeMap1.floorKey(8) + ",在表中所有<=8的数中，我离8最近");
        System.out.println(treeMap1.ceilingKey(8) + ",在表中所有>=8的数中，我离8最近");
        System.out.println(treeMap1.floorKey(7) + ",在表中所有<=7的数中，我离7最近");
        System.out.println(treeMap1.ceilingKey(7) + ",在表中所有>=7的数中，我离7最近");
        treeMap1.remove(5);
        System.out.println(treeMap1.get(5) + "，删了就没有了哦");
        System.out.println("================================================");
    }
}
# 单链表的节点结构
class Node<V> {
    V value;
    Node next;
}
由以上结构的节点依次连接起来所形成的链叫单链表结构。
# 双链表的节点结构
class Node<V> {
    V value;
    Node next;
    Node last;
}
由以上结构的节点依次连接起来所形成的链叫双链表结构。
单链表和双链表结构只需要给定一个头部节点 head，就可以找到剩下的所有节点。
# 反转单向和双向链表
  • 题目：分别实现反转单向链表和反转双向链表的函数。
  • 要求：如果链表长度为 N, 时间复杂度要求为 O (N), 额外空间复杂度要求为 O (1)。
  • 代码以后再贴。
# 打印两个有序表的公共部分
  • 题目：给定两个有序链表的头指针 head1 和 head2, 打印两个链表的公共部分。
  • 要求：如果两个链表的长度之和为 N, 时间复杂度要求为 O (N), 额外空间复杂度要求为 O (1)。
  • 代码以后再贴。
# 面试时链表解题的方法论
  1. 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度。
  2. 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法。
# 重要技巧
  1. 额外数据结构记录 (哈希表等)。
  2. 快慢指针。
# 判断一个链表是否为回文结构
  • 题目：给定一个单链表的头节点 head, 请判断该链表是否为回文结构。
  • 例子：1->2->1, 返回 true;1->2->2->1, 返回 true;15->6->15, 返回 true;1->2->3, 返回 false。
  • 例子：如果链表长度为 N，时间复杂度达到 O (N)，额外空间复杂度达到 O (1)。
Palindrome.java
import java.util.Stack;
/**
 * @Author: LightRain
 * @Description: 判断一个链表是否为回文结构
 * @DateTime: 2023-05-09 23:40
 * @Version：1.0
 **/
public class Palindrome {
    public static void main(String[] args) {
        // 测试不会写之后再补
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/9 23:41
     * @Param: [head]
     * @Return: boolean
     * @Description: need n extra space 需要 n 个额外的空间，压入到栈形式的回文
     * @since 17
     */
    public static boolean isPalindrome1(Node head) {
        // 创建 Stack 对象
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            // 将所有东西压入进栈内
            stack.push(cur);
            cur = cur.next;
        }
        // 不为空则继续遍历
        while (head != null) {
            // 栈弹出一个对比一个 全部都一样返回 true
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/9 23:53
     * @Param: [head]
     * @Return: boolean
     * @Description: need n/2 extra space 需要 n2 额外空间，二分之 N 方法查找快慢指针
     * @since 17
     */
    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<>();
        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;
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/10 0:33
     * @Param: [head]
     * @Return: boolean
     * @Description: need O (1) extra space 需要 O (1) 个额外空间实现判断一个链表是否为回文结构
     * @since 17
     */
    public static boolean isPalindrome3(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node n1 = head;
        Node n2 = head;
        //find mid node 查找中间节点
        //n2 走完 n1 会来到中点位置
        while (n2.next != null && n2.next.next != null) {
            //n1 一次走一步 n1 -> mid
            n1 = n1.next;
            //n2 一次走两步 n2 -> end
            n2 = n2.next.next;
        }
        //n2 -> right part first node 右部分第一节点
        n2 = n1.next;
        //mid.next -> null
        n1.next = null;
        Node n3 = null;
        //right part convert
        // 从 n1 开始逆序
        while (n2 != null) {
            // 右半部分开始逆序
            //n3 -> save next node 保存下一个节点
            n3 = n2.next;
            //next of right node convert 右节点转换的下一个
            n2.next = n1;
            //n1 move n1 移动
            n1 = n2;
            //n2 move n2 移动
            n2 = n3;
        }
        // 右边逆序到中点时
        //n3 -> save last node 保存最后一个节点
        n3 = n1;
        //n2 -> left first node 左第一节点
        n2 = head;
        boolean res = true;
        //check palindrome 检查回文
        // 左边一个点
        // 右边一个点
        while (n1 != null && n2 != null) {
            //n1 和 n2 每从一步验证一次，不一致 res 设置为 false
            if (n1.value != n2.value) {
                res = false;
                break;
            }
            //left to mid 左至中
            //n1 从中间走
            n1 = n1.next;
            //right to mid 从右边到中间
            //n2 也从中间走
            n2 = n2.next;
        }
        n1 = n3.next;
        n3.next = null;
        //recover list 恢复右半逆序链表
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }
    /**
     * 链表节点
     */
    private static class Node {
        public int value;
        public Node next;
        public Node(int value) {
            this.value = value;
        }
    }
}
# 将单向链表按照某值划分
  • 将单向链表按照某值划分成左边小、中间相等、右边大的形式。
  • 题目：给定一个单链表的头节点 head，节点的值类型是整形，再给定一个整数 pivot。
  • 实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于 pivot 的节点，右部分都是值大于 pivot 的节点。
【进阶】在实现原问题功能的基础上增加如下的要求
  1. 调整后所有小于 pivot 的节点之间的相对顺序和调整前一样。
  2. 调整后所有等于 pivot 的节点之间的相对顺序和调整前一样。
  3. 调整后所有大于 pivot 的节点之间的相对顺序和调整前一样。
  4. 时间复杂度请达到 O (N)，额外空间复杂度请达到 O (1)。
SmallerEqualBigger.java
/**
 * @Author: LightRain
 * @Description: 将单向链表按照某值划分成左边小、中间相等、右边大的形式。
 * @DateTime: 2023-05-10 00:51
 * @Version：1.0
 **/
public class SmallerEqualBigger {
    public static void main(String[] args) {
        // 测试不会写之后再补
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/10 1:05
     * @Param: [head, pivot]
     * @Return: com.example.cleanemptyfolders.sort.SmallerEqualBigger.Node
     * @Description: 列表分区
     * @since 17
     */
    public static Node listPartition(Node head, int pivot) {
        //small head 小于头
        Node sH = null;
        //small tail 小于尾
        Node sT = null;
        //equal head 等于头
        Node eH = null;
        //equal tail 等于尾
        Node eT = null;
        //big head 大于头
        Node mH = null;
        //big tail 大于尾
        Node mT = null;
        //save next node 保存下一个节点
        Node next = null;
        //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 {
                    // 如果不是第一个节点将老的尾巴链接到当前 head 节点
                    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 (mH == null) {
                    mH = head;
                    mT = head;
                } else {
                    mT.next = head;
                    mT = head;
                }
            }
            head = next;
        }
        //small and equal reconnect
        // 小而相等的重新连接
        if (sT != null) {
            sT.next = eH;
            // 下一步，谁去链接大于区域的头谁就变成 eT
            eT = eT == null ? sT : eT;
        }
        // 上面的 if, 不管跑了没有 eT
        //all reconnect 全部重新连接
        if (eT != null) {
            // 如果小于区域和等于区域，不是都没有
            eT.next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mH);
    }
    /**
     * 链表节点
     */
    private static class Node {
        public int value;
        public Node next;
        public Node(int value) {
            this.value = value;
        }
    }
}
# 复制含有随机指针节点的链表
  • 题目一种特殊的单链表节点类描述如下
    class Node{
        int value;
        Node next;
        Node rand;
        Node (int val){
            value = val;
        }     
    }
  • rand 指针是单链表节点结构中新增的指针，rand 可能指向链表中的任意一个节点，也可能指向 null。
  • 给定一个由 Node 节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】时间复杂度 O (N)，额外空间复杂度 O (1)
CopyListWithRand.java
import java.util.HashMap;
/**
 * @Author: LightRain
 * @Description: 复制含有随机指针节点的链表
 * @DateTime: 2023-05-10 01:47
 * @Version：1.0
 **/
public class CopyListWithRand {
    public static void main(String[] args) {
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/10 2:07
     * @Param: [head]
     * @Return: com.example.cleanemptyfolders.sort.CopyListWithRand.Node
     * @Description: 使用链表完成节点复制
     * @since 17
     */
    public static Node copyListWithRand1(Node head) {
        // 创建 Map
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            // 做出克隆节点添加到 map 内
            map.put(cur, new Node(cur.value));
            // 进行下一个节点
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            //cur 老链表
            //map.get (cur) 新链表
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            // 进行下一个节点
            cur = cur.next;
        }
        return map.get(head);
    }
    /**
     * @Author: LightRain
     * @Date: 2023/5/10 2:07
     * @Param: [head]
     * @Return: com.example.cleanemptyfolders.sort.CopyListWithRand.Node
     * @Description: 不使用链表完成节点复制
     * @since 17
     */
    public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        //copy node and link to every node 复制节点并链接到每个节点
        // 1->2->3
        // 1->1'->2->2'->3->3'
        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 设置复制节点 rand
        //1->1'->2->2'
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            // 如果 cur.rand != null 设置为 cur.rand.next 否则设置为 null
            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;
    }
    /**
     * 链表节点
     */
    private static class Node {
        public int value;
        public Node next;
        public Node rand;
        public Node(int value) {
            this.value = value;
        }
    }
}