【數據結構和演算法】001 單鏈表 LinkedList

 小朋友，你是否有很多問號？為什麼？別人都在看漫畫，而我在學畫畫，對著鋼琴說話...

一、單鏈表（LinkedList）介紹和記憶體佈局

鏈表是有序的列表，它在記憶體中的實際存儲結構如下：

 看上去雖然無序，但ta是靠每個鏈表節點元素的   地址  和  next域  來分清首尾相連的順序，如下圖所示，由頭指針指向第一個元素，進而第二個、三個...

鏈表的邏輯結構：

二、單鏈表創建、遍歷實現以及單鏈表節點增、刪、改、查操作

1、創建、新增、遍歷顯示

模型如下：1）head節點 2）中間節點 3）尾結點

                 每個節點的next域指向下一個節點的對象地址，尾結點為空

新建所需實體類：

package ...;

/**
 * @Author: ldk
 * @Date: 2020/3/29 21:18
 * @Describe:
 */
public class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;//指向下一個節點

    //構造節點對象
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    //重寫toString()

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }

//GetSet方法自行腦補....

}

創建 SingleLinkedList 類，編寫 添加 和 遍歷 的方法 並 創建main方法測試：

package ...;

/**
 * @Author: ldk
 * @Date: 2020/3/29 21:25
 * @Describe:
 */
public class LinkedListTest {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "張三", "小三");
        HeroNode h2 = new HeroNode(2, "李四", "小四");
        HeroNode h3 = new HeroNode(3, "王五", "小五");
        HeroNode h4 = new HeroNode(4, "趙六", "小六");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(h1);
        singleLinkedList.add(h2);
        singleLinkedList.add(h3);
        singleLinkedList.add(h4);
        singleLinkedList.detail();
    }

    static class SingleLinkedList {
        //創建頭結點
        private HeroNode head = new HeroNode(0, "", "");

        //節點添加方法
        public void add(HeroNode heroNode) {

            //拿到頭結點
            HeroNode temp = head;
            //找到最後一個節點，把next域指向要添加的節點
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = heroNode;
        }

        //顯示鏈表【遍歷】
        public void detail() {
            if (head.next == null) {
                System.out.println("鏈表為空！");
                return;
            }
            //獲取一個臨時指針
            HeroNode temp = head.next;
            while (true) {
                if (temp.next == null){
                    System.out.println(temp.toString());
                    System.out.println("就這麼多了~~");
                    break;
                }
                System.out.println(temp.toString());
                temp = temp.next;
            }
        }
    }
}

運行結果：

2、按順序插入節點

上面的測試是從1,2,3,4依次插入，那麼，鏈表本身是有序的，我們能不能按照no欄位亂序插入實現自動遞增排序，且從重覆元素不再重覆插入，

 意思就是，插入順序改成1432，但鏈表內部結構依然是1234

 代碼只需稍微對add（）方法修改一下：

        //按照欄位no 升序插入
        public void add2(HeroNode heroNode) {
            //獲取指針
            HeroNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                } else if (temp.next.no == heroNode.no) {
                    System.out.println("該節點已經存在~");
                    return;
                } else if (temp.next.no > heroNode.no) {
                    break;
                }
                temp = temp.next;
            }
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

凌亂且重覆的插入順序：

有序的列印結果：

依然是1234的順序，而且重覆的元素不再插入 ~

其餘增刪改查有時間可以做自己思考一下，這裡不再贅述。

三、單鏈表新浪、騰訊、百度面試題

 解答暫時值分析思路，代碼後期慢慢填補：

1）思路：從頭結點的下一個開始，一直遍歷，每遍歷一個即+1，直到.next為空，此所得即為鏈表長度

2）思路：依然是遍歷，從第一個一直遍歷到第length-k的下一個即為k

代碼（後補）：

3）思路：有點難度，但也是很清晰的。

分為母鏈和子鏈，母鏈雙指針，子鏈單指針

母鏈拆一個節點拼接到子鏈頭部後第一個，以此類推，得到的全新子鏈即為反轉鏈：

代碼（後補）：

4）思路：同4，反轉後，列印即可。

5）思路：以其中一個鏈表為母鏈，另一個為子鏈，遍歷子鏈，挨個插入母聯即可。

2020-03-29  21:02:13