鏈表是離散存儲線性結構，物理地址上不要求連續(xù)。
- 鏈表優(yōu)點
物理地址不需要連續(xù)，插入刪除元素比較快 - 鏈表缺點
查詢速度慢
現(xiàn)在用java來實現(xiàn)一個簡單的鏈表，其中涉及到的算法有：添加，刪除，查找，獲取結點個數(shù)，查找倒數(shù)第k個結點，兩個鏈表的公共結點。
-
鏈表結構
單向鏈表中主要由結點來體現(xiàn)的，而結點只包含兩個域，數(shù)據(jù)域data+指向下一個結點的引用。
鏈表.png
如下所示：
/*********************************************************************結點定義*********************************************************/
//構成鏈表的結點（此處是單鏈表，每個結點都保存了指向下一個結點的引用）
class Node{
public int data;
public Node next;
public Node(int data,Node next){
this.data = data;
this.next = next;
}
}
而鏈表只需要知道頭結點即可：
package com.wang.suan;
/**
* 鏈表
* @author wxe
* @since 0.0.1
*/
public class LinkedList {
private Node head;//頭結點
/*********************************************************************結點定義*********************************************************/
//構成鏈表的結點（此處是單鏈表，每個結點都保存了指向下一個結點的引用）
class Node{
public int data;
public Node next;
public Node(int data,Node next){
this.data = data;
this.next = next;
}
}
}
鏈表中只定義了一個頭結點，主要是為了方便其他比如遍歷，插入等方法。
-
插入結點
- 插入到尾結點
這里我們先來介紹一下，插入到尾結點的算法。如果要插入到尾結點，那么勢必需要先通過遍歷鏈表獲取到尾結點,時間復雜度為O(n)。比如我們要將value為data0數(shù)據(jù)插入到尾結點中：
圖片.png
接下來我們先遍歷找到尾結點，current當前指定的結點就是尾結點：
圖片.png
執(zhí)行插入時，新的結點就成了尾結點，其next指向null：
圖片.png
執(zhí)行插入操作，遍歷到的尾結點的next執(zhí)行新節(jié)點即可：
圖片.png
算法如下：
/**
* 插入結點(插入到尾結點)
* @param value
* @return
*/
public void insertTail(int value){
Node current = head;
Node newNode = new Node(value, null);
if (head == null) {
//1.首次插入，為頭結點
head = newNode;
} else {
//2.非首次插入,那么必須找到尾結點
while (current.next != null) {
current = current.next;
}
current.next = newNode;//將新節(jié)點添加到尾結點
}
}
- 插入到頭結點
有時候鏈表為了節(jié)省時間，就插在頭結點處。由于不用遍歷整個鏈表尋找尾結點，所以時間復雜度為O(n)，比如我們要將value為data0數(shù)據(jù)插入到頭結點中。
圖片.png
執(zhí)行插入操作，分兩步如下所示：
圖片.png
圖片.png
整理一下就是：
圖片.png
算法如下：
/**
* 插入頭結點，時間復雜度為O(1)
* @param value
*/
public void insertHead(int value){
Node newNode = new Node(value, null);
if (head != null) {
newNode.next = head.next;
}
head = newNode;
}
-
插入指定位置
插入指定位置，那么我們首先要找到這個位置上的結點，然后再執(zhí)行插入操作，比如將data0數(shù)據(jù)項插入到index為2的位置：
圖片.png
先找到index=2位置處的結點：
圖片.png
然后執(zhí)行插入操作：
圖片.png
圖片.png
整理一下就是：
圖片.png
實現(xiàn)代碼如下：
/**
* 指定位置添加結點,先遍歷鏈表找到index-1位置上的結點和index上的結點
* @param value
* @param index
*/
public void add(int value,int index){
Node newNode = new Node(value, null);
//1.檢驗插入位置是否合法
if (index <1 || index > size()) {
System.out.println("輸入位置不合法！");
return;
}
Node current = head;
int currentPos = 0;
while(current.next != null){
currentPos ++;
if (index == currentPos ) {
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
}
}
-
刪除結點
- 時間復雜度為O(n)
刪除結點，我們首先要知道刪除的那個結點位置，還要知道刪除結點的前一個結點和后一個結點。然后直接將要刪除結點的前一個結點的next指向后一個結點即可。但是我們不需要注意到這個結點是否為空，是否為頭結點，是否為尾結點等邊界條件，由于需要遍歷需要這個結點，因此其時間復雜度為O(n).比如我們要刪除數(shù)據(jù)項為data2的結點。
圖片.png
首先我們要找到刪除的結點delNode和前一個結點preNode:
圖片.png
然后直接將preNode的next指向delNode的next，然后清空delNode就可以了。
圖片.png
實現(xiàn)代碼如下：
/**
* 刪除指定結點，首先要找到刪除的結點的位置,還必須找到該節(jié)點的前置，后置結點。O(n)時間復雜度
* @param value
* @return
*/
public void delete(int value){
Node current = head;
Node preNode = head;
Node delNode = null;
while (current.next != null) {
if (current.data == value) {
delNode = current;
break;
}
preNode = current;
current = current.next;
}
if (delNode == null) {
return ;
}
if (delNode == head) {
//如果刪除的是頭結點
head = delNode.next;
} else if (delNode.next == null) {
//如果刪除的是尾結點
preNode.next = null;
} else {
preNode.next = delNode.next;
}
delNode = null;
}
-
時間復雜度為O(1)
劍指offer中有一道關于刪除鏈表的算法題，給定頭結點，和一個結點指針，要求時間復雜度為O(1)時間刪除該結點。首先我們需要明白給定的這個結點指針，不僅有值，而且還有指向下一個結點的引用。那么就是說，如果我們將下一個結點的值復制到該結點中，再將下一個結點的next指向復制給該節(jié)點的next。好像就實現(xiàn)了刪除這個結點的操作。但是這是建立在這個結點必須存在于鏈表中，而且該節(jié)點不能為尾結點，因為如果為尾結點的話，還是需要遍歷整個鏈表的。這樣一來時間復雜度為 O(n)。我們計算一下平均復雜度為：[（n-1）*O(n) + O(n) ] / n ，時間復雜度其實還是O(1)是符合要求的。比如要刪除delNode = new Node(data2,nextNode)：
圖片.png
首先將nextNode中的數(shù)據(jù)項復制到要刪除的node中
圖片.png
然后再將該結點的next指向nextNode的next，如圖所示：
圖片.png
如果正好只有一個結點的話，head結點直接為null了。
或者刪除的是尾結點，那么必須遍歷了，參考上面O(n)算法刪除操作。
實現(xiàn)代碼如下：
/**
* 刪除結點(O(1)時間復雜度)，可以用被刪除結點的下一個結點P1覆蓋被刪除的結點P2，然后再刪除P1結點即可。
* @param value
*/
public void deleteNode(Node delNode){
if (head == null) {
return;
}
//如果刪除的不是尾結點
if (delNode.next != null) {
//1.找到下一個結點
Node nextNode = delNode.next;
//2.復制下一個結點給要刪除的結點
delNode.data = nextNode.data;
delNode.next = nextNode.next;
nextNode = null;//方便回收
}
//如果正好只有一個結點，頭結點就是尾結點
else if (head == delNode) {
head = null;
delNode = null;
}
//鏈表中有多個結點，刪除尾結點
else {
Node current = head;
while (current.next != delNode) {
current = current.next;
}
current.next = null;
delNode = null;
}
}
-
查找倒數(shù)第k個結點
要查找倒數(shù)第k個結點，假設鏈表有n個結點，那么第K個結點就是從前到后遍歷到的第n-k+1個結點。這個時候我們有一種思路就是遍歷一遍鏈表知道這個鏈表的結點數(shù)n，然后再遍歷一遍鏈表找到第n-k+1結點，就是所謂的第K個結點。但是這樣一來，相當于我們遍歷了兩次鏈表。我們還可以使用一些技巧只遍歷一次鏈表就可以了。我們可以定義兩個指針，一個指針preKNode先向前走k-1個位置，然后另一個指針current和preKNode同時遍歷鏈表，直到preKNode遍歷到尾結點，那么current指向的就是倒數(shù)第k個結點。比如我們要找到倒數(shù)第2個結點，也就是數(shù)據(jù)項為data2的結點。分析如下：
圖片.png
現(xiàn)在先讓preKNode向前走k-1步，也就是1步：
圖片.png
然后兩個指針同時向前走，直到preKNode到達尾結點：
圖片.png
圖片.png
那么current指針指向的就是倒數(shù)第K個結點了。
實現(xiàn)代碼如下：
/**
* 查找倒數(shù)第k個結點
* @param value
* @param k
* @return
*/
public Node findKNode(int k){
Node current = head;
Node preKNode = head;
//preKNode為第k-1個結點
for (int i = 0; i < k-1; i++) {
preKNode = preKNode.next;
}
//當?shù)趉-1的結點遍歷到了尾結點，current就是第k個結點
while (preKNode.next != null) {
preKNode = preKNode.next;
current = current.next;
}
return current;
}
-
反轉鏈表
比如我們通過遍歷鏈表的方式來反轉如下鏈表：
圖片.png
首先，我們定義兩個指針，分別指向相鄰的兩個結點一個是current，一個是preNode，我們只需要將current的next指向上一個結點preNode，就相當于做了一次反轉，可是我們知道current.next指向preNode時，相當于data1和data2兩個結點斷了關系，沒有辦法繼續(xù)遍歷下去了。此時，我們在斷開data1和data2之前就需要一個臨時結點保存tempNode來保存data1的next,也就是tempNode = current.next;這樣才能繼續(xù)保持遍歷鏈表。
第一次反轉，頭結點相當于尾結點了。
第一次反轉.png
繼續(xù)向下遍歷
圖片.png
繼續(xù)向下遍歷
圖片.png
繼續(xù)向下走：
圖片.png
此時反轉完成，而preNode成為了新的頭結點，直接返回即可。
實現(xiàn)代碼如下：
/**
* 反轉鏈表，并返回頭結點
*
* @return
*/
public Node reverse() {
//空鏈表
if (head == null) {
return head;
}
//只有一個結點
if (head.next == null) {
return head;
}
Node preNode = head;// 上一結點
Node current = head.next;// 當前結點
Node tempNode = null;
while (current != null) {
tempNode = current.next;
if (preNode == head) {
preNode.next = null;
}
current.next = preNode;//指針方向反轉
preNode = current;//preNode向前移動
current = tempNode;//current向前移動
}
return preNode;
}
-
合并兩個排序的鏈表
比如對這兩個鏈表進行排序
圖片.png
其實，這里就是通過遍歷兩個鏈表，通過比較兩個鏈表的結點然后找到合適的合并后的結點。如下所示：
圖片.png
我們來進行第一次比較，也就是找到第一個合適的合并后的結點mergeNode。由于p1.data < p2.data，因此，此時mergeNode應該指向p1，如下所示：
圖片.png
找到了頭結點，我們來找一下mergeNode的下一個結點，開始第二次比較：
圖片.png
繼續(xù)比較，尋找mergeNode的下一個結點，開始第三次比較：
圖片.png
依次類推下去，我們知道每次找到了mergeNode其實我們都用了相同的比較方法來尋找其下一個結點，這種就可以用遞歸的方法來表達了。知道最后完成比較并排序，結果如下所示：
圖片.png
實現(xiàn)代碼如下：
/**
* 用遞歸方式合并兩個有序鏈表，并保持合并后的鏈表有序
* @param head1
* @param head2
* @return
*/
public Node mergeList(Node head1,Node head2){
Node mergedNode = null; //合并后的結點
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
if (head1.data < head2.data) {
mergedNode = head1;
mergedNode.next = mergeList(head1.next, head2);
} else {
mergedNode = head2;
mergedNode.next = mergeList(head1, head2.next);
}
return mergedNode;
}
-
兩個鏈表的第一個公共結點
題目是：輸入兩個鏈表，找到他們的第一個公共結點。
先來理解一下這個題目哈，找到第一個公共節(jié)點，那說明這個公共結點之后的結點都是一樣的。所以，從第一個公共節(jié)點開始之后的結點都是重合的?？雌饋硐窳艘粋€Y字。比如，下面兩個鏈表：
圖片.png
那么其實這個時候，我們肯定不能通過遍歷一個鏈表（m個結點），然后再另個一個鏈表（n個結點）中找到相同數(shù)據(jù)項的結點，這樣子的算法相當于是O(mn)的時間效率。
可以這么考慮，如果我們保持兩個鏈表長度相同，同時遍歷鏈表然后進行比較。這樣提高了時間效率。但是給出的鏈表長度是未知的，不一定是相同的，這個時候，我們需要以長度短的鏈表為主來尋找第一個公共結點。也就是說，鏈表比較長的，我們先要走一定的步數(shù)，讓其保持和另一個鏈表長度一致，然后再同時遍歷比較。
實現(xiàn)代碼如下：
/**
* 查找第一個公共祖先
* @param head1
* @param head2
* @return
*/
public Node findFirstCommonNode(Node head1,Node head2){
if (head1 == null || head2 == null) {
return null;
}
int size1 = size(head1);
int size2 = size(head2);
int diff = size1 - size2;
Node longNode = head1;
Node shortNode = head2;
if (diff < 0) {
diff = size2 - size1;
longNode = head2;
shortNode = head1;
}
//讓長的鏈表先走diff步
for (int i = 0; i < diff; i++) {
longNode = longNode.next;
}
//現(xiàn)在長度一致同時遍歷
while (longNode != null && shortNode != null && longNode.data != shortNode.data) {
longNode = longNode.next;
shortNode = shortNode.next;
}
return longNode;
}
public int size(Node head) {
int size = 0;
if (head == null) {
return size;
}
while (head.next != null) {
head = head.next;
size++;
}
return size + 1;// 加上最后一個尾結點個數(shù)
}
-
尋找中間結點
設置一個快慢指針，快指針P2每次走兩步，慢指針P1每次走一步，由于快指針P2走的快，因此要注意結束條件以P2為主。比如我們要尋找下面這個鏈表的中間結點：
圖片.png
P1走一步，P2走兩步，如下所示：
圖片.png
由上面我們可以看到P2只能走一步，沒有辦法再走兩步了，因此這里已經(jīng)達到結束時間了。P1指向的就是中間結點。
或者我們看看鏈表長度為奇數(shù)時：
圖片.png
P1走一步，P2走兩步，如下所示：
圖片.png
P2此時沒法走兩步，達到結束條件。P1指向的就是中間結點。
代碼實現(xiàn)如下：
/**
* 查找中間結點
* @return
*/
public Node findMiddleNode(Node head){
Node p1 = head;
Node p2 = head;
if (head == null) {
//空鏈表
return null;
} else if (head.next == null) {
//只有一個結點
return head;
} else {
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
}
return p1;
}
最后附上所有的源代碼
package com.wang.suan;
/**
* 鏈表
*
* @author wxe
* @since 0.0.1
*/
public class LinkedList {
private Node head;// 頭結點
/******************************************************* 鏈表的增刪改查操作 *********************************************************************/
/**
* 插入結點(插入到尾結點)
*
* @param value
* @return
*/
public void insertTail(int value) {
Node current = head;
Node newNode = new Node(value, null);
if (head == null) {
// 1.首次插入，為頭結點
head = newNode;
} else {
// 2.非首次插入,那么必須找到尾結點
while (current.next != null) {
current = current.next;
}
current.next = newNode;// 將新節(jié)點添加到尾結點
}
}
/**
* 插入頭結點，時間復雜度為O(1)
*
* @param value
*/
public void insertHead(int value) {
Node newNode = new Node(value, null);
if (head != null) {
newNode.next = head.next;
}
head = newNode;
}
/**
* 查找結點
*
* @param value
* @return
*/
public Node find(int value) {
Node current = head;
while (current.next != null) {
if (current.data == value) {
return current;
}
current = current.next;
}
return null;
}
/**
* 刪除指定結點，首先要找到刪除的結點的位置,還必須找到該節(jié)點的前置，后置結點。O(n)時間復雜度
*
* @param value
* @return
*/
public void delete(int value) {
Node current = head;
Node preNode = head;
Node delNode = null;
while (current.next != null) {
if (current.data == value) {
delNode = current;
break;
}
preNode = current;
current = current.next;
}
if (delNode == null) {
return;
}
if (delNode == head) {
// 如果刪除的是頭結點
head = delNode.next;
} else if (delNode.next == null) {
// 如果刪除的是尾結點
preNode.next = null;
} else {
preNode.next = delNode.next;
}
delNode = null;
}
/**
* 刪除結點(O(1)時間復雜度)，可以用被刪除結點的下一個結點P1覆蓋被刪除的結點P2，然后再刪除P1結點即可。
*
* @param value
*/
public void deleteNode(Node delNode) {
if (head == null) {
return;
}
// 如果刪除的不是尾結點
if (delNode.next != null) {
// 1.找到下一個結點
Node nextNode = delNode.next;
// 2.復制下一個結點給要刪除的結點
delNode.data = nextNode.data;
delNode.next = nextNode.next;
nextNode = null;// 方便回收
}
// 如果正好只有一個
else if (head == delNode) {
head = null;
delNode = null;
}
// 鏈表中有多個結點，刪除尾結點
else {
Node current = head;
while (current.next != delNode) {
current = current.next;
}
current.next = null;
delNode = null;
}
}
/**
* 指定位置添加結點,先遍歷鏈表找到index-1位置上的結點和index上的結點
*
* @param value
* @param index
*/
public void add(int value, int index) {
Node newNode = new Node(value, null);
// 1.檢驗插入位置是否合法
if (index < 1 || index > size()) {
System.out.println("輸入位置不合法！");
return;
}
Node current = head;
int currentPos = 0;
while (current.next != null) {
currentPos++;
if (index == currentPos) {
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
}
}
/**
* 獲取結點個數(shù)
*
* @return
*/
public int size() {
int size = 0;
if (head == null) {
return 0;
}
Node current = head;
while (current.next != null) {
current = current.next;
size++;
}
return size + 1;// 加上最后一個尾結點個數(shù)
}
public int size(Node head) {
int size = 0;
if (head == null) {
return size;
}
while (head.next != null) {
head = head.next;
size++;
}
return size + 1;// 加上最后一個尾結點個數(shù)
}
/**
* 查找倒數(shù)第k個結點
*
* @param value
* @param k
* @return
*/
public Node findKNode(int k) {
Node current = head;
Node preKNode = head;
// preKNode為第k-1個結點
for (int i = 0; i < k - 1; i++) {
preKNode = preKNode.next;
}
// 當?shù)趉-1的結點遍歷到了尾結點，current就是第k個結點
while (preKNode.next != null) {
preKNode = preKNode.next;
current = current.next;
}
return current;
}
/**
* 反轉鏈表，并返回頭結點
*
* @return
*/
public Node reverse() {
//空鏈表
if (head == null) {
return head;
}
//只有一個結點
if (head.next == null) {
return head;
}
Node preNode = head;// 上一結點
Node current = head.next;// 當前結點
Node tempNode = null;
while (current != null) {
tempNode = current.next;
if (preNode == head) {
preNode.next = null;
}
current.next = preNode;//指針方向反轉
preNode = current;//preNode向前移動
current = tempNode;//current向前移動
}
return preNode;
}
/**
* 用遞歸方式合并兩個有序鏈表，并保持合并后的鏈表有序
* @param head1
* @param head2
* @return
*/
public Node mergeList(Node head1,Node head2){
Node mergedNode = null; //合并后的結點
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
if (head1.data < head2.data) {
mergedNode = head1;
mergedNode.next = mergeList(head1.next, head2);
} else {
mergedNode = head2;
mergedNode.next = mergeList(head1, head2.next);
}
System.out.println(mergedNode.data);
return mergedNode;
}
/**
* 查找第一個公共祖先
* @param head1
* @param head2
* @return
*/
public Node findFirstCommonNode(Node head1,Node head2){
if (head1 == null || head2 == null) {
return null;
}
int size1 = size(head1);
int size2 = size(head2);
int diff = size1 - size2;
Node longNode = head1;
Node shortNode = head2;
if (diff < 0) {
diff = size2 - size1;
longNode = head2;
shortNode = head1;
}
//讓長的鏈表先走diff步
for (int i = 0; i < diff; i++) {
longNode = longNode.next;
}
//現(xiàn)在長度一致同時遍歷
while (longNode != null && shortNode != null && longNode.data != shortNode.data) {
longNode = longNode.next;
shortNode = shortNode.next;
}
return longNode;
}
/**
* 查找中間結點
* @return
*/
public Node findMiddleNode(Node head){
Node p1 = head;
Node p2 = head;
if (head == null) {
//空鏈表
return null;
} else if (head.next == null) {
//只有一個結點
return head;
} else {
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
}
return p1;
}
public void display() {
if (head != null) {
while (head.next != null) {
System.out.println(head.data);
}
}
}
/********************************************************************* 結點定義 *********************************************************/
// 構成鏈表的結點（此處是單鏈表，每個結點都保存了指向下一個結點的引用）
class Node {
public int data;
public Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
/**************************************************** *********測試鏈表 ******************************************************************/
public static void main(String[] args) {
// LinkedList list = new LinkedList();
// list.insertTail(1);
// list.insertTail(2);
// list.insertTail(3);
// list.insertTail(4);
//
//
//
// System.out.println(list.head.data);
// // System.out.println(list.find(6));
// // System.out.println(list.size());
// System.out.println(list.findKNode(2).data);
//// list.reverse();
// System.out.println(list.reverse().data);
// System.out.println(list.findKNode(2).data);
LinkedList list = new LinkedList();
list.insertTail(1);
list.insertTail(2);
list.insertTail(5);
list.insertTail(7);
list.insertTail(9);
LinkedList list2= new LinkedList();
list2.insertTail(2);
list2.insertTail(4);
list2.insertTail(8);
// System.out.println(list.mergeList(list.head, list2.head).data);
// System.out.println(list.findFirstCommonNode(list.head, list2.head).data);
System.out.println(list.findMiddleNode(list.head).data);
}
}
