1. Java 實現鏈表的數據結構

主要的實現方式是在類中設置一個 Node 的內部類，用來存儲鏈表的節點

/**
 * 鏈表數據結構聯系
 *
 * @author Jiantao Yan
 * @title: MyLink
 * @date 2020/3/23 18:32
 */
public class MyLink {

    Node head = null;

    /**
     * 鏈表數據結構
     */
    class Node {
        Node next = null;
        int data;
        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 添加元素
     * @param data
     */
    public void add(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            return;
        }

        Node pointer = head;
        while (pointer.next != null) {
            pointer = pointer.next;
        }
        pointer.next = node;

    }
    
    /**
     * 將元素添加到指定的下標
     * @param data  數據
     * @param index 下標
     */
    public void add(int data, int index) {
        // 得到鏈表長度
        int length = length();
        if (index <0 || index > length) {
            System.out.println("數組下標錯誤");
            return;
        }

        Node node = new Node(data);
        if (index == 0) {
            node.next = head;
            head = node;
            return;
        }

        int i = 1;
        Node preNode = head;
        Node curNode = head.next;
        while (curNode != null) {
            if (i == index) {
                node.next = preNode.next;
                preNode.next = node;
                return;
            }
            if (i == length+1) {
                curNode.next = node;
            }
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }
        preNode.next = node;

    }

    /**
     * 根據鏈表下標刪除鏈表
     * @param index 元素的下標
     * @return  是否刪除成功
     */
    public boolean delete(int index) {
        // 得到鏈表長度
        int length = length();

        // 數組下標錯誤
        if (index < 0 || index > length) {
            System.out.println("下標錯誤");
            return false;
        }

        // 刪除第一個元素
        if (index == 0) {
            head = head.next;
            return true;
        }

        // 刪除中間末尾元素
        Node preNode = head;
        Node curNode = head.next;
        int i = 1;
        while (curNode != null) {
            if (i == index) {
                preNode.next = curNode.next;
                return true;
            }
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }

        preNode.next = null;
        return true;
    }

    /**
     * 計算鏈表的長度
     * @return  鏈表的長度
     */
    public int length() {
        int length = 0;

        Node pointer = head;
        while (pointer != null) {
            pointer = pointer.next;
            length++;
        }
        return length;
    }

    @Override
    public String toString() {
        if (head == null) {
            System.out.println("鏈表為空");
            return "鏈表為空";
        }

        StringBuffer sb = new StringBuffer();

        Node pointer = head;
        while (pointer.next != null) {
            sb.append(pointer.data).append("->");
            pointer = pointer.next;
        }
        sb.append(pointer.data);
        return sb.toString();
    }


}

2. 鏈表常用的算法

以下算法均寫在 MyLink 類中

2.1 單鏈表反轉

使用數組暫存方式

    /**
     * 鏈表反轉
     * 將鏈表數據放入一個數組中
     * 再次新建一個鏈表
     */
    public void reverseLink1() {

        int length = this.length();

        int [] arr = new int[length];

        if (head == null || head.next == null) {
            return;
        }

        int i = 0;
        Node pointer = head;
        while (pointer != null) {
            arr[i] = pointer.data;
            pointer = pointer.next;
            i++;
        }

        head = new Node(arr[length -1]);
        Node pointer2 = head;
        for (int j = 0; j < length -1; j++) {

            pointer2.next = new Node(arr[length-j-2]);
            pointer2 = pointer2.next;

        }

    }

使用鏈表逆轉方法

    /**
     * 鏈表反轉算法-2
     * next 指向 head.next 的下個節點 (前移一位）
     * head.next 指向 pre 上個節點 （指針反向）
     * pre 指向 head 節點 （前移一位）
     * head 指向 next 節點 （前移一位）
     * 動圖地址：https://boolean-dev.oss-cn-hangzhou.aliyuncs.com/blog/file/2020-03/v2-c434ed3a1a229820ae04b07f26896d32_b.webp
     */
    public void reverseLink2() {
        if (head ==null || head.next == null) {
            return;
        }

        Node preNode = null;
        Node nextNode = null;
        while (head != null) {
            nextNode = head.next;
            head.next = preNode;
            preNode = head;
            head = nextNode;
        }
    }

翻轉動圖：

為鏈表加環

此處環為首尾相連

    /**
     * 為鏈表添加一個環
     * @param data  data
     */
    public void addRing(int data) {
        Node node = new Node(data);

        if (head == null) {
            head = node;
            return;
        }
        node.next = head;

        Node pointer = head;
        while (pointer.next != null) {
            pointer = pointer.next;
        }
        pointer.next = node;
    }

鏈表環的檢測

    /**
     * 檢測是否有環
     * 快慢指針方法
     * @return  環的位置
     */
    public int checkRing() {
        if (head == null) {
            System.out.println("鏈表為空");
            return 0;
        }

        Node one = head;
        Node two = head.next.next;
        int index = 0;
        while (one.next != null) {
            if (one.next == two.next) {
                break;
            }
            one = one.next;
            if (two.next != null && two.next.next != null) {
                two = two.next.next;
            }else {
                return -1;
            }

            index++;
        }
        return index;
    }

2.3 兩個有序的鏈表合并

我這寫的是兩個鏈表合并，例如1->2->3->4和2->3->4，這里合并為1->2->3->4->2->3->4。但是我覺得題目的意思是合并為1->2->2->3->3->4->4，我這里應該寫錯了

    /**
     * 合并兩個鏈表
     * @param second    待合并鏈表
     */
    public void merge(MyLink second) {
        if (head == null) {
            head = second.head;
        }

        // 遍歷到第一個鏈表結尾
        Node pointer = head;
        while (pointer.next != null) {
            pointer = pointer.next;
        }
        pointer.next = second.head;
    }

2.4 刪除鏈表倒數第 n 個結點

    /**
     * 刪除倒數第 N 個數據
     * 使用快慢指針，快指針比慢指針先走 N 個元素
     * 隨后快慢指針同樣的速度走，當快指針走到終點，即找到了要刪除的元素
     * @param reciprocalIndex   刪除的倒數下標位置
     * @return  刪除是否成功
     */
    public boolean deleteReciprocal(int reciprocalIndex) {
        int length = this.length();

        if (reciprocalIndex > length-1) {
            System.out.println("數組下標越界");
            return false;
        }

        Node slow = head;
        Node fast = head;
        for (int i = 0; i < reciprocalIndex; i++) {
            fast = fast.next;
        }
        int index = 0;
        Node preNode = null;
        while (fast.next != null) {
            preNode = slow;
            slow = slow.next;
            fast = fast.next;
            index++;
        }

        // 第一個節點
        if(preNode == null) {
            head = head.next;
        }else {
            preNode.next = slow.next;
        }
        
        return true;
    }

2.5 求鏈表的中間結點

    /**
     * 查找中間節點
     * 利用快慢指針，快指針比慢指針每步多走一步
     * 當快指針走到末尾，慢指針走到中間
     * 注意鏈表奇偶長度判斷，此處偶數取中間靠右節點
     * @return  中間節點數據
     */
    public int findMid() {
        
        // 如果為空鏈表，則返回-1
        if (head == null) {
            return -1;
        }
        
        // 如果節點只有一個，則直接返回第一個
        if (head.next == null) {
            return head.data;
        }
        
        // 快慢指針查找中點
        boolean isSinger = true;
        Node slow = head;
        Node fast = head;
        while (fast.next != null) {
            if (fast.next.next == null) {
                isSinger = false;
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 判斷長度為雙還是為單
        if (isSinger) {
            return slow.data;
        }else {
            return slow.next.data;
        }
    }