## 一：單向鏈表基本介紹 鏈表是一種數據結構，和數組同級。比如，Java中我們使用的ArrayList，其實現原理是數組。而LinkedList的實現原理就是鏈表了。鏈表在進行循環遍歷時效率不高，但是插入和刪除時優勢明顯。下面對單向鏈表做一個介紹。 單向鏈表是一種線性表，實際上是由節點（Node）組成的，一個鏈表擁有不定數量的節點。其數據在內存中存儲是不連續的，它存儲的數據分散在內存中，每個結點只能也只有它能知道下一個結點的存儲位置。由N各節點（Node）組成單向鏈表，每一個Node記錄本Node的數據及下一個Node。向外暴露的只有一個頭節點（Head），我們對鏈表的所有操作，都是直接或者間接地通過其頭節點來進行的。  上圖中最左邊的節點即為頭結點（Head），但是添加節點的順序是從右向左的，添加的新節點會被作為新節點。最先添加的節點對下一節點的引用可以為空。引用是引用下一個節點而非下一個節點的對象。因為有著不斷的引用，所以頭節點就可以操作所有節點了。? 下圖描述了單向鏈表存儲情況。存儲是分散的，每一個節點只要記錄下一節點，就把所有數據串了起來，形成了一個單向鏈表。?  節點（Node）是由一個需要儲存的對象及對下一個節點的引用組成的。也就是說，節點擁有兩個成員：儲存的對象、對下一個節點的引用。下面圖是具體的說明：  ## 二、單項鏈表的實現 ~~~ /** * @author Administrator */ public class MyLink { Node head = null; // 頭節點 /** * 鏈表中的節點，data代表節點的值，next是指向下一個節點的引用 * * @author zjn * */ class Node { Node next = null;// 節點的引用，指向下一個節點 int data;// 節點的對象，即內容 public Node(int data) { this.data = data; } } /** * 向鏈表中插入數據 * * @param d */ public void addNode(int d) { Node newNode = new Node(d);// 實例化一個節點 if (head == null) { head = newNode; return; } Node tmp = head; while (tmp.next != null) { tmp = tmp.next; } tmp.next = newNode; } /** * * @param index:刪除第index個節點 * @return */ public boolean deleteNode(int index) { if (index < 1 || index > length()) { return false; } if (index == 1) { head = head.next; return true; } int i = 1; Node preNode = head; Node curNode = preNode.next; while (curNode != null) { if (i == index) { preNode.next = curNode.next; return true; } preNode = curNode; curNode = curNode.next; i++; } return false; } /** * * @return 返回節點長度 */ public int length() { int length = 0; Node tmp = head; while (tmp != null) { length++; tmp = tmp.next; } return length; } /** * 在不知道頭指針的情況下刪除指定節點 * * @param n * @return */ public boolean deleteNode11(Node n) { if (n == null || n.next == null) { return false; } int tmp = n.data; n.data = n.next.data; n.next.data = tmp; n.next = n.next.next; System.out.println("刪除成功！"); return true; } public void printList() { Node tmp = head; while (tmp != null) { System.out.println(tmp.data); tmp = tmp.next; } } public static void main(String[] args) { MyLink list = new MyLink(); list.addNode(5); list.addNode(3); list.addNode(1); list.addNode(2); list.addNode(55); list.addNode(36); System.out.println("linkLength:" + list.length()); System.out.println("head.data:" + list.head.data); list.printList(); list.deleteNode(4); System.out.println("After deleteNode(4):"); list.printList(); } } ~~~ ## 三、鏈表相關的常用操作實現方法 1\. 鏈表反轉 直接改變頭尾指向即可 ~~~ /** * 鏈表反轉 * * @param head * @return */ public Node ReverseIteratively(Node head) { Node pReversedHead = head; Node pNode = head; Node pPrev = null; while (pNode != null) { Node pNext = pNode.next; if (pNext == null) { pReversedHead = pNode; } pNode.next = pPrev; pPrev = pNode; pNode = pNext; } this.head = pReversedHead; return this.head; } ~~~ 2\. 查找單鏈表的中間節點 采用快慢指針的方式查找單鏈表的中間節點，快指針一次走兩步，慢指針一次走一步，當快指針走完時，慢指針剛好到達中間節點。 ~~~ /** * 查找單鏈表的中間節點 * * @param head * @return */ public Node SearchMid(Node head) { Node p = this.head, q = this.head; while (p != null && p.next != null && p.next.next != null) { p = p.next.next; q = q.next; } System.out.println("Mid:" + q.data); return q; } ~~~ 3\. 查找倒數第k個元素 采用兩個指針P1,P2，P1先前移K步，然后P1、P2同時移動，當p1移動到尾部時，P2所指位置的元素即倒數第k個元素 。 ~~~ /** * 查找倒數 第k個元素 * * @param head * @param k * @return */ public Node findElem(Node head, int k) { if (k < 1 || k > this.length()) { return null; } Node p1 = head; Node p2 = head; for (int i = 0; i < k; i++)// 前移k步 p1 = p1.next; while (p1 != null) { p1 = p1.next; p2 = p2.next; } return p2; } ~~~ 4\. 對鏈表進行排序 ~~~ /** * 排序 * * @return */ public Node orderList() { Node nextNode = null; int tmp = 0; Node curNode = head; while (curNode.next != null) { nextNode = curNode.next; while (nextNode != null) { if (curNode.data > nextNode.data) { tmp = curNode.data; curNode.data = nextNode.data; nextNode.data = tmp; } nextNode = nextNode.next; } curNode = curNode.next; } return head; } ~~~ 5\. 刪除鏈表中的重復節點 ~~~ /** * 刪除重復節點 */ public void deleteDuplecate(Node head) { Node p = head; while (p != null) { Node q = p; while (q.next != null) { if (p.data == q.next.data) { q.next = q.next.next; } else q = q.next; } p = p.next; } } ~~~ 6\. 從尾到頭輸出單鏈表，采用遞歸方式實現 ~~~ /** * 從尾到頭輸出單鏈表，采用遞歸方式實現 * * @param pListHead */ public void printListReversely(Node pListHead) { if (pListHead != null) { printListReversely(pListHead.next); System.out.println("printListReversely:" + pListHead.data); } } ~~~ [](javascript:void(0); "復制代碼") 7\. 判斷鏈表是否有環，有環情況下找出環的入口節點 [](javascript:void(0); "復制代碼") ~~~ /** * 判斷鏈表是否有環，單向鏈表有環時，尾節點相同 * * @param head * @return */ public boolean IsLoop(Node head) { Node fast = head, slow = head; if (fast == null) { return false; } while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { System.out.println("該鏈表有環"); return true; } } return !(fast == null || fast.next == null); } /** * 找出鏈表環的入口 * * @param head * @return */ public Node FindLoopPort(Node head) { Node fast = head, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) break; } if (fast == null || fast.next == null) return null; slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } ~~~ 轉載自：https://blog.csdn.net/jianyuerensheng/article/details/51200274