鏈表，如其名，是一個表，被鏈子連接起來的表
正如資料結構基礎中說資料在計算機中存盤的方式有兩種，資料存盤和鏈式存盤，順序存盤就是大家常用的陣列，鏈式存盤就是這里我們要講的了，順序存盤就是說資料在記憶體中存盤的位置是聯系的，鏈式存盤也就是非連續。那么鏈式存盤是靠什么聯系在一起的呢！就是我們剛才說的“鏈子”，那么這個鏈子是什么呢！
這個鏈子是我們自己定義的，我們可以定義一條鏈子，把一個資料與他前面的資料聯系在一起，這樣我們就可以通過上一個資料順著鏈子找到下一個資料，這就是資料結構中的單鏈表。單鏈表如其名，我們只能順著鏈子，從前往后找，假設我們要找的資料在這個鏈表的最后面，找起來時間就會很長，所以，我們可以用兩條鏈子連接資料，一條鏈子連接前面的資料，一條鏈子連接后面的資料，這樣既可以在前面查找，也可以在后面查找。這就是雙鏈表。
我們可以自己創建一個鏈表類。
public class ListNode {
int var;
ListNode next;
ListNode(int x) {
this.var = x;
}
ListNode（）{
this.var=0;
this.next=null;
}
}這就是一個最簡單的單鏈表類，在這個類中，我們用變數var存盤資料，采用物件next連接下一個物件。同樣的我們還可以創建一個雙鏈表類
public class ListNode {
int var;
ListNode prev;
ListNode next;
ListNode(int x) {
this.var = x;
}
ListNode（）{
this.var=0;
this.prev=null;
this.next=null;
}
}這就是最簡單的一個雙鏈表類，在這里我們定義了兩個構造方法，這樣可以允許創建空鏈表，同樣的，采用變數var存盤資料，添加了prev連接前一個物件。當然在這兩個鏈表存盤結構中，我們完全可以var的型別換成Object，因為int型別存盤的資料太小了。這個可以按照需求來自行設定。鏈表最基本的屬性創建完成了，下面可以定義一些常用的方法。
我們最常用的方法有print、insert、remove、replace。
鏈表的遍歷，代碼如下：
public void print(ListNode l1) {
ListNode head=l1;
while(head.next!=null) {
System.out.print(head.var+" ");
head=head.next;
}
}public void remove(ListNode listnode) {
listnode.var=listnode.next.var;
listnode.next=listnode.next.next;
}方法有很多，只寫了兩種，簡單來說，鏈表的操作其實就是指標的修改，單鏈表修改一個指標，雙鏈表就需要修改兩個指標。而且可以發現鏈表的方法運行所需要的時間和占有的空間都是比較小的，原因就是指標的原因。
下面以Leetcode中的例題來深入了解一下鏈表的
easy
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
通過次數318,650提交次數502,3
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作權歸領扣網路所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
public ListNode mergerTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.var < l2.var) {
l1.next = mergerTwoLists(l1, l2.next);
return l1;
} else {
l2.next = mergerTwoLists(l2, l1.next);
return l2;
}
}該題我們采用了遞回的方法，是一個不斷轉換指標的程序。不斷判斷小的節點，然后對指標進行變換，該題的思路容易想出來，但是解題程序每人不同，該解題程序為官方解答，簡潔明了，該題比較簡單，容易理解，可以當作一個練習來做。
給定兩個（單向）鏈表，判定它們是否相交并回傳交點。請注意相交的定義基于節點的參考，而不是基于節點的值。換句話說，如果一個鏈表的第k個節點與另一個鏈表的第j個節點是同一節點（參考完全相同），則這兩個鏈表相交。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節點的值為 8 （注意，如果兩個串列相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci
著作權歸領扣網路所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
public ListNode solution(ListNode head1,ListNode head2) {
if(head1==null||head2==null) {
return null;
}
while(head1!=head2) {
head1=head1==null?head2:head1.next;
head2=head2==null?head1:head2.next;
}
return head1;
}這個程序第一眼看到是錯的，但是自習品，發現，寫的是真的NB，可以看一下，該題也比較簡單，最基本的暴力解法是采用雙指標的形式。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/34325.html
標籤：非技術區
上一篇：Java
下一篇：JAVA excel匯出