目錄

鏈表的介紹

單鏈表的手動實現

單鏈表的基本框架

打印鏈表：

獲取表長：

頭插法新增節點：

尾插法新增節點：

在指定下標插入：

鏈表的查找

?刪除鏈表中第一個出現的key：

刪除鏈表中所有key值

鏈表置空

?總代碼

測試代碼

?鏈表相關的OJ題

1.反轉單鏈表

?思路：?

2.查找鏈表中間節點

?思路：1.判空；2.定義兩個指針，都指向head；3.設置循環，每次循環一個指針走兩步一個指針走一步，當走的快的那個指針到達最后一個節點時，慢的節點就在中間；

---

鏈表的介紹

基于順序表具有，插入數據，空間不足時要擴容，擴容有性能消耗和插入刪除數據時有時候需要大量的挪動數據，導致程序的執行效率低的缺點，延升出了鏈表。

鏈表，是一種邏輯結構連續物理結構不一定連續的一種數據結構；由一個個的節點組成，每個節點包含數據域和指針域，指針域指向下一個節點。

單鏈表的手動實現

單鏈表的基本框架

//不帶頭結點的單鏈表
public class MySingleList implements IList{//鏈表由若干個頭結點組成，每個節點都是一個完整的部分，所以可以定義一個內部類static class ListNode{public int val;//數據域public ListNode next;//指針域 存放下一個節點的地址public ListNode(int val) {this.val = val;}}public ListNode head;//定義一個存放節點的變量，默認值為null@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}
}

為了更好的理解這個單鏈表的操作，我們先創建單鏈表的方法：

    public ListNode head;//定義一個存放節點的變量，默認值為nullpublic void createList(){//1.通過實例化ListNode創建幾個節點ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(22);ListNode node3 = new ListNode(32);ListNode node4 = new ListNode(42);//2.根據單鏈表的形態，把節點鏈接起來node1.next = node2;node2.next = node3;node3.next = node4;this.head = node1;}

打印鏈表：

    public void display() {//1.借助一個cur節點去遍歷鏈表，移動cur的位置ListNode cur = head;while (cur !=null){//cur=null表示整個鏈表都走完了System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}

注意區分循環條件?cur !=null 和cur.next?!=null

獲取表長：

獲取表長的方法是打印方法衍生出來的，無非就是打印的方法中加一個計數器去記表長：

    public int size() {ListNode cur = head;int count = 0;while (cur != null){//注意這個循環條件count++;cur = cur.next;}return count;}

頭插法新增節點：

    public void addFirst(int data) {//1.實例化一個節點ListNode node = new ListNode(data);//2.新增節點的指針域指向頭節點更新頭結點 順序不可變node.next = head;this.head = node;}

?注意：

• 插入數據時先綁定后面，如果我們先綁定前面的話會發生什么呢？當this.head = node先執行的完后，新增節點指針域該指向誰了，為了防止數據丟失，插入數據時因先綁定后面

尾插法新增節點：

    public void addLast(int data) {ListNode node = new ListNode(data);//1.找到鏈表最后一個節點if (head == null){head = node;}else {//遍歷鏈表去找ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node ;//增}}

在指定下標插入：

    public void addIndex(int index, int data) {//1.判斷index的合法性if (index < 0 || index > size()){throw new IndexException("index非法"+index);}//表空的情況ListNode node = new ListNode(data);if (head == null){head = node;return;}//2.在0位置插入時調用頭插if (index == 0 ){addFirst(data);return;}//3.index=size（）尾插法if (index == size()){addLast(data);return;}//在index位置插入時，找到index位置的前一個節點去操作ListNode cur = findPrevIndex(index);node.next = cur.next;cur.next = node;}private ListNode findPrevIndex(int index){ListNode cur = head;int count = 0;while (count != index - 1){count++;cur = cur.next;}return cur;}

鏈表的查找

    public boolean contains(int key) {ListNode cur = head;while (cur !=null){if (cur.val == key){return true;}cur = cur.next;}return false;}

?刪除鏈表中第一個出現的key：

   public void remove(int key) {//1.表空if (head == null){return;}//2.頭結點刪除if (head.val == key){head = head.next;return;}//3.中間元素刪除找key的前驅節點去操作ListNode cur = findPrevKey(key);cur.next = cur.next.next;//也可以借助一個變量去刪除/*ListNode del = cur.next;cur.next = del.next;*/}//盡量以方法的方式去實現功能，降低代碼的耦合度private ListNode findPrevKey(int key){ListNode cur = head;while (cur.next !=null){if (cur.next.val == key){return cur;}else {cur = cur.next;}}return null;}

刪除鏈表中所有key值

    public void removeAllKey(int key) {if (head == null) {return;}//定義兩個指針分別指向頭和頭的下一個ListNode prev = head;ListNode cur = head.next;//可能要被移除的元素while (cur != null) {//遍歷if (cur.val == key) {prev.next = cur.next;cur = cur.next;} else {//不用刪除就往后繼續遍歷prev = cur;cur = cur.next;}//此時除了頭結點其他節點都遍歷完了，就判斷頭節點if (head.val == key) {head = head.next;}}}

鏈表置空

    public void clear() {//法1：循環把每個節點都置空//法2：直接把最開始的節點中（只要是沒有人引用的對象內存都會回收置空），這樣就把整個鏈表置空了head = null;}

?總代碼

//不帶頭結點的單鏈表
public class MySingleList implements IList{//鏈表由若干個頭結點組成，每個節點都是一個完整的部分，所以可以定義一個內部類static class ListNode{public int val;//數據域public ListNode next;//指針域 存放下一個節點的地址public ListNode(int val) {this.val = val;}}public ListNode head;//定義一個存放節點的變量，默認值為nullpublic void createList(){//1.通過實例化ListNode創建幾個節點ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(22);ListNode node3 = new ListNode(32);ListNode node4 = new ListNode(42);//2.根據單鏈表的形態，把節點鏈接起來node1.next = node2;node2.next = node3;node3.next = node4;this.head = node1;}@Overridepublic void addFirst(int data) {//1.實例化一個節點ListNode node = new ListNode(data);//2.新增節點的指針域指向頭節點更新頭結點node.next = head;this.head = node;}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);//1.找到鏈表最后一個節點if (head == null){head = node;}else {//遍歷鏈表去找ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node ;//增}}@Overridepublic void addIndex(int index, int data) {//1.判斷index的合法性if (index < 0 || index > size()){throw new IndexException("index非法"+index);}//表空的情況ListNode node = new ListNode(data);if (head == null){head = node;return;}//2.在0位置插入時調用頭插if (index == 0 ){addFirst(data);return;}//3.index=size（）尾插法if (index == size()){addLast(data);return;}//在index位置插入時，找到index位置的前一個節點去操作ListNode cur = findPrevIndex(index);node.next = cur.next;cur.next = node;}private ListNode findPrevIndex(int index){ListNode cur = head;int count = 0;while (count != index - 1){count++;cur = cur.next;}return cur;}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur !=null){if (cur.val == key){return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {//1.表空if (head == null){return;}//2.頭結點刪除if (head.val == key){head = head.next;return;}//3.中間元素刪除找key的前驅節點去操作ListNode cur = findPrevKey(key);cur.next = cur.next.next;//也可以借助一個變量去刪除/*ListNode del = cur.next;cur.next = del.next;*/}//盡量以方法的方式去實現功能，降低代碼的耦合度private ListNode findPrevKey(int key){ListNode cur = head;while (cur.next !=null){if (cur.next.val == key){return cur;}else {cur = cur.next;}}return null;}@Overridepublic void removeAllKey(int key) {if (head == null) {return;}//定義兩個指針分別指向頭和頭的下一個ListNode prev = head;ListNode cur = head.next;//可能要被移除的元素while (cur != null) {//遍歷if (cur.val == key) {prev.next = cur.next;cur = cur.next;} else {//不用刪除就往后繼續遍歷prev = cur;cur = cur.next;}//此時除了頭結點其他節點都遍歷完了，就判斷頭節點if (head.val == key) {head = head.next;}}}@Overridepublic int size() {ListNode cur = head;int count = 0;while (cur != null){count++;cur = cur.next;}return count;}@Overridepublic void clear() {//法1：循環把每個節點都置空//法2：直接把最開始的節點中（只要是沒有人引用的對象內存都會回收置空），這樣就把整個鏈表置空了head = null;}@Overridepublic void display() {if (head == null){System.out.println("鏈表為空");return;}//1.借助一個cur節點去遍歷鏈表，移動cur的位置ListNode cur = head;while (cur !=null){//cur=null表示整個鏈表都走完了System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}}

測試代碼

public class Test {public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.createList();System.out.println();mySingleList.display();//12 22 32 42System.out.println(mySingleList.size());//4mySingleList.addFirst(2);mySingleList.display();//2 12 22 32 42mySingleList.addLast(52);mySingleList.display();//2 12 22 32 42 52mySingleList.addIndex(2,20);mySingleList.display();//2 12 20 22 32 42 52System.out.println(mySingleList.contains(52));//truemySingleList.remove(12);mySingleList.display();//2 20 22 32 42 52mySingleList.addLast(2);mySingleList.addIndex(3,2);mySingleList.display();//2 20 22 2 32 42 52 2mySingleList.removeAllKey(2);mySingleList.display();//20 22 32 42 52mySingleList.clear();mySingleList.display();//鏈表為空}
}

?鏈表相關的OJ題

1.反轉單鏈表

反轉一個單鏈表

?思路：

    public ListNode reverseList(){if (head == null){return null;}if (head.next == null){return head;}//ListNode cur = head.next;//定義一個cur記錄當前需要反轉的節點head.next = null;while(cur != null){ListNode curNext = cur.next;//記錄下一個反轉點cur.next = head;//當前要反轉的節點指向headhead = cur;//更新headcur = curNext;//更新cur}return head;}

2.查找鏈表中間節點

題目

?思路：1.判空；2.定義兩個指針，都指向head；3.設置循環，每次循環一個指針走兩步一個指針走一步，當走的快的那個指針到達最后一個節點時，慢的節點就在中間；

    public ListNode middleNode(){if (head == null){return null;}ListNode fast = head;ListNode slow = head;while (fast != null && fast.next !=null){//順序不能反，否則報空指針異常fast = fast.next.next;slow = slow.next;}return slow;}

?感謝大家閱讀📚點贊👍收藏?評論?關注?

博客主頁： 【長毛女士-CSDN博客】?