数据结构重点内容

一.单链表

基于java实现：

// 节点类
class Node{
    int data;
    Node next;


    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Node(int data){
        this.data = data;
        this.next = null;
    }
}
// 链表类
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        head = null;
    }

    // 向链表结尾插入数据
    public void addNode(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
        }
        else {
            Node temp = head;
            while(temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }

    // 获取链表长度
    public int length(){
        Node temp = head;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    // 删除下标为 n 的节点 ,这里假设头节点算第1个节点
    public boolean deleteNode(int n) {
        int length = length();
        if(n<1 || n>length) return false;

        if(n==1) {
            head = head.next;
            return true;
        }

        // 找到要删除节点的前一个节点
        Node temp = head;
        int count = 1;
        while(count<n-1) {
            count++;
            temp = temp.next;
        }
        // 删除节点（无论是中间节点还是尾节点）
        temp.next = temp.next.next;
        return true;
    }

    // 在不知道头节点的情况下删除指定节点
    public boolean deleteAnyNode(Node n){
        // 该节点为空或者是尾节点，就无法删除
        if(n==null || n.next==null) return false;
        // 将下一个节点的数据复制到当前节点
        n.data=n.next.data;
        // 跳过下一个节点（相当于删除了当前节点的数据）
        n.next = n.next.next;
        return true;
    }

    public void printList(){
        Node temp = head;
        while(temp!=null){
            System.out.print(temp.data+" ");
            temp = temp.next;
        }
    }

    // 链表反转,迭代法
    public Node reverseList(Node head){
        if(head==null || head.next==null) return head;
        Node prev = null;   // 前一个节点
        Node curr = head;   // 当前节点
        Node next = null;   // 下一个节点
        while(curr!=null){
            next = curr.next;   // 保存下一个节点
            curr.next = prev;   // 反转当前节点的指向 ,这一步是核心,上一步的顺序不能交换
            prev = curr;        // 移动prev指针
            curr = next;        // 移动current指针
        }
        head = prev;            // 反转后prev成为新的头节点
        return head;
    }

    // 寻找链表中间节点
    public Node findMid(Node head){
        if(head == null ) return null;
        Node fast = head;
        Node slow = head;
        // 如果长度为奇数，则fast在最后一个节点停下，若为偶数，则在倒数第二个节点停下
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 查找链表倒数第k个元素
    public Node findK(Node head,int k){
        if(head == null || k<1) return null;
        Node fast = head;
        Node slow = head;
        for(int i=0;i<k;i++){
            // 如果k大于链表长度，提前返回空
            if(fast==null) return null;
            fast = fast.next;  // 快指针移动k步
        }
        while(fast!=null){   // 快慢指针之间应该相差k个节点，如k=2 slow在倒数第二个，则fast在尾节点之后（null）
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    // 对链表排序,基于归并排序
    public void mergeSort(){
        head = mergeSort(head);
    }
    private Node mergeSort(Node head){
        // 空链表或单个链表无需排序
        if(head==null || head.next==null) return head;

        // 先找中间节点，用来拆分链表
        Node mid = findMid(head);
        Node rightHead = mid.next;
        // 切断链表
        mid.next = null;

        // 分别对左右两端链表递归调用
        Node left = mergeSort(head);
        Node right = mergeSort(rightHead);

        return merge(left,right);
    }
    // 合并两段链表
    private Node merge(Node left,Node right){
        Node res = new Node(0);
        Node curr = res;
        // 合并处理
        while(left!=null&&right!=null){
            if(left.data<right.data){
                curr.next = left;
                left = left.next;
            }else{
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        // 处理剩余节点
        if(left!=null){
            curr.next = left;
        }
        if(right!=null){
            curr.next = right;
        }
        return res.next;
    }

    // 删除链表的重复节点,保留1个节点，前提链表有序
    public void deleteDuplicates(Node head){
        if(head==null || head.next==null) return;
        Node curr = head;
        while(curr!=null && curr.next!=null){
            if(curr.data==curr.next.data){
                curr.next = curr.next.next;
            }else{
                curr = curr.next;
            }
        }
    }

    // 判断链表是否有环，如有则找到入口
    public boolean isLoop(Node head){
        Node fast = head;
        Node slow = head.next;
        while(fast!=slow){
            if(fast==null || fast.next==null) return false; // 能到末尾说明无环
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    // 确定有环，找到环的入口
    public Node findStart(Node head){
        // 先找到快慢指针第一次相遇的节点
        Node fast = head;
        Node slow = head;
        while(fast!=slow){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 找到后将slow移动到头节点
        slow = head;
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}