Java順序表和鏈表如何實現(xiàn)

這篇“Java順序表和鏈表如何實現(xiàn)”文章的知識點大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java順序表和鏈表如何實現(xiàn)”文章吧。

1. 線性表

線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串…

線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。

2. 順序表

其實就是一個數(shù)組?！驹鰟h查改】那為什么還有寫一個順序表，直接用數(shù)組就好了嘛？不一樣，寫到類里面 將來就可以 面向?qū)ο罅恕?/p>

2.1 概念及結(jié)構(gòu)

順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。

順序表一般可以分為：

• 靜態(tài)順序表：使用定長數(shù)組存儲。

• 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。

靜態(tài)順序表適用于確定知道需要存多少數(shù)據(jù)的場景.

靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪費，開少了不夠用.

相比之下動態(tài)順序表更靈活, 根據(jù)需要動態(tài)的分配空間大小.

2.2 接口實現(xiàn)

我們來實現(xiàn)一個動態(tài)順序表. 以下是需要支持的接口.

這里我們挨個拆解出來：

public class MyArrayList {

    public int[] elem;
    public int usedSize;//有效的數(shù)據(jù)個數(shù)

    public MyArrayList() {
        this.elem = new int[10];
    }
    // 打印順序表public void display() {
    
    }
    System.out.println();}// 獲取順序表長度public int size() {
    return 0;}// 在 pos 位置新增元素public void add(int pos, int data) {}// 判定是否包含某個元素public boolean contains(int toFind) {
    return true;}// 查找某個元素對應(yīng)的位置public int search(int toFind) {
    return -1;}// 獲取 pos 位置的元素public int getPos(int pos) {
    return -1;}// 給 pos 位置的元素設(shè)為 valuepublic void setPos(int pos, int value) {}//刪除第一次出現(xiàn)的關(guān)鍵字keypublic void remove(int toRemove) {}// 清空順序表public void clear() {}}

這是我們順序表的基本結(jié)構(gòu)。下面我們就把順序表的功能一個一個拆解出來：


打印數(shù)據(jù)表：

public void display() {
    for (int i = 0; i < this.usedSize; i++) {
        System.out.print(this.elem[i] + " ");
    }
    System.out.println();}

獲取順序表長度：


public int size() {
    return this.usedSize;}

public void add(int pos, int data) {
    if(pos < 0 || pos > this.usedSize) {
        System.out.println("pos 位置不合法");
        return;
    }
    if(isFull()){
        this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
    }
    for (int i = this.usedSize-1; i >= pos; i--) {
        this.elem[i + 1] = this.elem[i];
    }
    this.elem[pos] = data;
    this.usedSize++;}//判斷數(shù)組元素是否等于有效數(shù)據(jù)個數(shù)public boolean isFull() {
    return this.usedSize == this.elem.length;}

public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (this.elem[i] == toFind) {
            return true;
        }
    }
    return false;}

public int search(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (this.elem[i] == toFind) {
            return i;
        }
    }
    return -1;}

public int getPos(int pos) {
    if (pos < 0 || pos >= this.usedSize){
        System.out.println("pos 位置不合法");
        return -1;//所以 這里說明一下,業(yè)務(wù)上的處理，這里不考慮
    }
    if(isEmpty()) {
        System.out.println("順序表為空！");
        return -1;
    }
    return this.elem[pos];}//判斷數(shù)組鏈表是否為空public boolean isEmpty() {
    return this.usedSize == 0;}

public void setPos(int pos, int value) {
    if(pos < 0 || pos >= this.usedSize) {
        System.out.println("pos 位置不合法");
        return;
    }
    if(isEmpty()) {
        System.out.println("順序表為空！");
        return;
    }
    this.elem[pos] = value;}//判斷數(shù)組鏈表是否為空public boolean isEmpty() {
    return this.usedSize == 0;}

public void remove(int toRemove) {
    if(isEmpty()) {
        System.out.println("順序表為空！");
        return;
    }
    int index = search(toRemove);//index記錄刪除元素的位置
    if(index == -1) {
        System.out.println("沒有你要刪除的數(shù)字！");
    }
    for (int i = index; i < this.usedSize - 1; i++) {
        this.elem[i] = this.elem[i + 1];
    }
    this.usedSize--;
    //this.elem[usedSize] = null;引用數(shù)組必須這樣做才可以刪除}

public void clear() {
    this.usedSize = 0;}

2.3 順序表的問題及思考

1. 順序表中間/頭部的插入刪除，時間復(fù)雜度為O(N)

2. 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。

3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當(dāng)前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間。

思考： 如何解決以上問題呢？下面給出了鏈表的結(jié)構(gòu)來看看。

3. 鏈表

3.1 鏈表的概念及結(jié)構(gòu)

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。

實際中鏈表的結(jié)構(gòu)非常多樣，如果按一般來分的話就是四種：

• 單向鏈表

• 雙向鏈表

• 循環(huán)鏈表

• 雙向循環(huán)鏈表

如果細(xì)分的話就有以下情況組合起來就有8種鏈表結(jié)構(gòu)：

• 單向、雙向

• 帶頭、不帶頭

• 循環(huán)、非循環(huán)

這八種分別為：

• 單向 帶頭 循環(huán)

• 單向 不帶頭 循環(huán)

• 單向 帶頭 非循環(huán)

• 單向 不帶頭 非循環(huán)

• 雙向 帶頭 循環(huán)

• 雙向 不帶頭 循環(huán)

• 雙向 帶頭 非循環(huán)

• 雙向 不帶頭 非循環(huán)

注：上述加粗是我們重點需要學(xué)習(xí)的?。?！

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們重點掌握兩種:

• 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

head：里面存儲的就是第一個節(jié)點(頭節(jié)點)的地址

head.next：存儲的就是下一個節(jié)點的地址

尾結(jié)點：它的next域是一個null

• 無頭雙向鏈表：在Java的集合框架庫中LinkedList底層實現(xiàn)就是無頭雙向循環(huán)鏈表。

最上面的數(shù)字是我們每一個數(shù)值自身的地址。

prev：指向前一個元素地址

next：下一個節(jié)點地址

data：數(shù)據(jù)

3.2 鏈表的實現(xiàn)

3.2.1無頭單向非循環(huán)鏈表的實現(xiàn)

上面地址為改結(jié)點元素的地址

val：數(shù)據(jù)域

next：下一個結(jié)點的地址

head：里面存儲的就是第一個結(jié)點(頭結(jié)點)的地址

head.next：存儲的就是下一個結(jié)點的地址

無頭單向非循環(huán)鏈表實現(xiàn):

class ListNode {
    public int val;
    public ListNode next;//ListNode儲存的是結(jié)點類型

    public ListNode (int val) {
        this.val = val;
    }}public class MyLinkedList {
    public ListNode head;//鏈表的頭引用

    public void creatList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;
    }
    //查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
    public boolean contains(int key) {
        
        return true;
    }
    //得到單鏈表的長度
    public int size(){
        return -1;
    }
    //頭插法
    public void addFirst(int data) {

    }
    //尾插法
    public void addLast(int data) {

    }
    //任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
    public boolean addIndex(int index,int data) {
        return true;
    }
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
    public void remove(int key) {

    }
    //刪除所有值為key的節(jié)點
    public ListNode removeAllKey(int key) {

    }
    //打印鏈表中的所有元素
    public void display() {

    }
    //清除鏈表中所有元素
    public void clear() {
        
    }}

上面是我們鏈表的初步結(jié)構(gòu)(未給功能賦相關(guān)代碼，大家可以復(fù)制他們到自己的idea中進(jìn)行練習(xí)，答案在下文中) 這里我們將他們一個一個拿出來實現(xiàn) 并實現(xiàn)！


打印鏈表中所有元素：

public void display() {
    ListNode cur = this.head;
    while(cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();}

查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中：


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

public int size(){
    int count = 0;
    ListNode cur = this.head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;}

public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = this.head;
    this.head = node;
    /*if (this.head == null) {
        this.head = node;
    } else {
        node.next = this.head;
        this.head = node;
    }*/}

public void addLast(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
    } else {
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }}

/**
 * 找到index - 1位置的節(jié)點的地址
 * @param index
 * @return
 */public ListNode findIndex(int index) {
    ListNode cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    return cur;}//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo)public void addIndex(int index,int data) {
    if(index < 0 || index > size()) {
        System.out.println("index 位置不合法！");
        return;
    }
    if(index == 0) {
        addFirst(data);
        return;
    }
    if(index == size()) {
        addLast(data);
        return;
    }
    ListNode cur = findIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;}

注意：單向鏈表找cur時要-1，但雙向鏈表不用 直接返回cur就好


刪除第一次出現(xiàn)關(guān)鍵字為key的結(jié)點：

/**
 * 找到 要刪除的關(guān)鍵字key的節(jié)點
 * @param key
 * @return
 */public ListNode searchPerv(int key) {
    ListNode cur = this.head;
    while(cur.next != null) {
        if(cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    return null;}//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點public void remove(int key) {
    if(this.head == null) {
        System.out.println("單鏈表為空");
        return;
    }
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    ListNode cur = searchPerv(key);
    if(cur == null) {
        System.out.println("沒有你要刪除的節(jié)點");
        return;
    }
    ListNode del = cur.next;
    cur.next = del.next;}

刪除所有值為key的結(jié)點：


public ListNode removeAllKey(int key) {
    if(this.head == null) {
        return null;
    }
    ListNode prev = this.head;
    ListNode cur = this.head.next;
    
    while(cur != null) {
        if(cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        } else {
            prev = cur;
            cur = cur.next;
        }
    }
        //最后處理頭
    if(this.head.val == key) {
        this.head = this.head.next;
    }
    return this.head;}

public void clear() {
    while (this.head != null) {
        ListNode curNext = head.next;
        head.next = null;
        head.prev = null;
        head = curNext;
    }
    last = null;}

3.2.2無頭雙向非循環(huán)鏈表實現(xiàn)：

上面的地址0x888為該結(jié)點的地址

val：數(shù)據(jù)域

prev：上一個結(jié)點地址

next：下一個結(jié)點地址

head：頭結(jié)點 一般指向鏈表的第一個結(jié)點

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

    public ListNode (int val) {
        this.val = val;
    }}public class MyLinkedList {
    public ListNode head;//指向雙向鏈表的頭結(jié)點
    public ListNode last;//只想雙向鏈表的尾結(jié)點
    //打印鏈表
    public void display() {

    }
    //得到單鏈表的長度
    public int size() {
        return -1;
    }
    //查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
    public boolean contains(int key) {
        return true;
    }
    //頭插法
    public void addFirst(int data) {

    }
    //尾插法
    public void addLast(int data) {

    }
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
    public void remove(int key) {

    }
    //刪除所有值為key的節(jié)點
    public void removeAllKey(int key) {

    }
    //任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
    public boolean addIndex(int index,int data) {
        return true;
    }
    //清空鏈表
    public void clear() {

    }}

上面是我們鏈表的初步結(jié)構(gòu)(未給功能賦相關(guān)代碼，大家可以復(fù)制他們到自己的idea中進(jìn)行練習(xí)，答案在下文中) 這里我們將他們一個一個拿出來實現(xiàn) 并實現(xiàn)！


打印鏈表：

public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();}

得到單鏈表的長度：


public int size() {
    ListNode cur = this.head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;}

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

public void addFirst(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    } else {
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }}

public void addLast(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    } else {
        ListNode lastPrev = this.last;
        this.last.next = node;
        this.last = this.last.next;
        this.last.prev = lastPrev;
        /**
         * 兩種方法均可
         * this.last.next = node;
         * node.prev = this.last;
         * this.last = node;
         */
    }}

注：第一種方法是先讓last等于尾結(jié)點 再讓他的前驅(qū)等于上一個地址 而第二種方法是先使插入的尾結(jié)點的前驅(qū)等于上一個地址 再使其等于尾結(jié)點

刪除第一次出現(xiàn)關(guān)鍵字為key的結(jié)點:

public void remove(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            if (cur == head) {
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    last = null;
                }
            } else if (cur == last) {
                last = last.prev;
                last.next = null;
            } else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
            return;
        }
        cur = cur.next;
    }}

刪除所有值為key的結(jié)點:

public void removeAllKey(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            if (cur == head) {
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    last = null;
                }
            } else if (cur == last) {
                last = last.prev;
                last.next = null;
            } else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
            //return;
        }
        cur = cur.next;
    }}

注：他和remove的區(qū)別就是刪除完后是不是直接return返回，如果要刪除所有的key值則不return，讓cur繼續(xù)往后面走。

任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo)：

public void addIndex(int index,int data) {
    if (index < 0 || index > size()) {
        System.out.println("index 位置不合法");
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    ListNode cur = searchIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur;
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;}public ListNode searchIndex(int index) {
    ListNode cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return cur;}

思路：先判斷 在頭位置就頭插 在尾位置就尾插 在中間就改變四個位置的值。


注意：單向鏈表找cur時要-1，但雙向鏈表不用 直接返回cur就好

清空鏈表：

public void clear() {
    while (this.head != null) {
        ListNode curNext = head.next;
        head.next = null;
        head.prev = null;
        head = curNext;
    }
    last = null;}

3.3 鏈表面試題

3.3.1反轉(zhuǎn)鏈表：

這里的

cur = this.head;

prev = null;

curNext = cur.next;

public ListNode reverseList() {
    if (this.head == null) {
        return null;
    }
    ListNode cur = this.head;
    ListNode prev = null;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = prev;
        prev = cur;
        cur = curNext;
    }
    return prev;}

3.3.2找到鏈表的中間結(jié)點：


public  ListNode middleNode() {
    if (head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        if (fast == null) {
            return slow;
        }
        slow = slow.next;
    }
    return slow;}

3.3.3輸入一個鏈表 返回該鏈表中倒數(shù)第k個結(jié)點

public ListNode findKthToTail(ListNode head,int k) {
    if (k <= 0 || head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (k - 1 != 0) {
        fast = fast.next;
        if (fast == null) {
            return null;
        }
        k--;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;}

3.3.4合并兩個鏈表 并變成有序的

public  static  ListNode mergeTwoLists(ListNode headA,ListNode headB) {
    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;
    while (headA != null && headB != null) {
        if(headA.val <headB.val) {
            tmp.next = headA;
            headA = headA.next;
            tmp = tmp.next;
        } else {
            tmp.next = headB;
            headB = headB.next;
            tmp = tmp.next;
        }
    }
    if (headA != null) {
        tmp.next = headA;
    }
    if (headB != null) {
        tmp.next = headB;
    }
    return newHead.next;}

最后返回的是傀儡結(jié)點的下一個 即newHead.next


3.3.5 編寫代碼，以給定值x為基準(zhǔn)將鏈表分割成兩部分，所有小于x的結(jié)點排在大于或等于x的結(jié)點之前 。(即將所有小于x的放在x左邊，大于x的放在x右邊。且他們本身的排序不可以變)

//按照x和鏈表中元素的大小來分割鏈表中的元素public ListNode partition(int x) {
    ListNode bs = null;
    ListNode be = null;
    ListNode as = null;
    ListNode ae = null;
    ListNode cur = head;
    while (cur != null) {
        if(cur.val < x){
            //1、第一次
            if (bs == null) {
                bs = cur;
                be = cur;
            } else {
                //2、不是第一次
                be.next = cur;
                be = be.next;
            }
        } else {
            //1、第一次
            if (as == null) {
                as = cur;
                as = cur;
            } else {
                //2、不是第一次
                ae.next = cur;
                ae = ae.next;
            }
        }
        cur = cur.next;
    }
    //預(yù)防第1個段為空
    if (bs == null) {
        return as;
    }
    be.next = as;
    //預(yù)防第2個段當(dāng)中的數(shù)據(jù)，最后一個節(jié)點不是空的。
    if (as != null) {
        ae.next = null;
    }
    return be;}

3.3.6 在一個排序的鏈表中，存在重復(fù)的結(jié)點，請刪除該鏈表中重復(fù)的結(jié)點，重復(fù)的結(jié)點不保留，返回鏈表頭指針。(有序的鏈表中重復(fù)的結(jié)點一定是緊緊挨在一起的)

public ListNode deleteDuplication() {
    ListNode cur = head;
    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;
    while (cur != null) {
        if (cur.next != null && cur.val == cur.next.val) {
            while (cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            //多走一步
            cur = cur.next;
        } else {
            tmp.next = cur;
            tmp = tmp.next;
            cur = cur.next;
        }
    }
    //防止最后一個結(jié)點的值也是重復(fù)的
    tmp.next = null;
    return newHead.next;}

3.3.7 鏈表的回文結(jié)構(gòu)。

public boolean chkPalindrome(ListNode head) {
    if (head == null) {
        return true;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //slow走到了中間位置
    ListNode cur = slow.next;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curNext;
    }
    //反轉(zhuǎn)完成
    while (head != slow) {
        if(head.val != slow.val) {
            return false;
        } else {
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    return true;}

3.3.8 輸入兩個鏈表，找出它們的第一個公共結(jié)點。

他是一個Y字形

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pl = headA;
    ListNode ps = headB;
    int lenA = 0;
    int lenB = 0;
    //求lenA的長度
    while (pl != null) {
        lenA++;
        pl = pl.next;
    }
    pl = headA;
    //求lenB的長度
    while (ps != null) {
        lenB++;
        ps = ps.next;
    }
    ps = headB;
    int len = lenA - lenB;//差值步
    if (len < 0) {
        pl = headB;
        ps = headA;
        len = lenB - lenA;
    }
    //1、pl永遠(yuǎn)指向了最長的鏈表，ps永遠(yuǎn)指向了最短的鏈表   2、求到了插值len步
    //pl走差值len步
    while (len != 0) {
        pl = pl.next;
        len--;
    }
    //同時走直到相遇
    while (pl != ps) {
        pl = pl.next;
        ps = ps.next;
    }
    return pl;}

3.3.9 給定一個鏈表，判斷鏈表中是否有環(huán)。

提問：為啥么fast一次走兩步，不走三步？

答：如果鏈表只有兩個元素他們則永遠(yuǎn)相遇不了(如上圖的示例2)，而且走三步的效率沒有走兩步的效率高。

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;}

3.3.10 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }
    if (fast == null || fast.next == null) {
        return null;
    }
    fast = head;
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;}

4. 順序表和鏈表的區(qū)別和聯(lián)系

4.1順序表和鏈表的區(qū)別

順序表：一白遮百丑

白：空間連續(xù)、支持隨機(jī)訪問

丑：

• 中間或前面部分的插入刪除時間復(fù)雜度O(N)

• 增容的代價比較大。

鏈表：一(胖黑)毀所有

胖黑：以節(jié)點為單位存儲，不支持隨機(jī)訪問

所有：

• 任意位置插入刪除時間復(fù)雜度為O(1)

• 沒有增容問題，插入一個開辟一個空間。

組織：

1、順序表底層是一個數(shù)組，他是一個邏輯上和物理上都是連續(xù)的

2、鏈表是一個由若干結(jié)點組成的一個數(shù)據(jù)結(jié)構(gòu)，邏輯上是連續(xù)的 但是在物理上[內(nèi)存上]是不一定連續(xù)的。

操作：

1、順序表適合，查找相關(guān)的操作，因為可以使用下標(biāo)，直接獲取到某個位置的元素

2、鏈表適合于，頻繁的插入和刪除操作。此時不需要像順序表一樣，移動元素。鏈表的插入 只需要修改指向即可。

3、順序表還有不好的地方，就是你需要看滿不滿，滿了要擴(kuò)容，擴(kuò)容了之后，不一定都能放完。所以，他空間上的利用率不高。

4.2數(shù)組和鏈表的區(qū)別

鏈表隨用隨取 要一個new一個

而數(shù)組則不一樣 數(shù)組是一開始就確定好的

4.3AeeayList和LinkedList的區(qū)別

集合框架當(dāng)中的兩個類

集合框架就是將 所有的數(shù)據(jù)結(jié)構(gòu)，封裝成Java自己的類

以后我們要是用到順序表了 直接使用ArrayList就可以。

以上就是關(guān)于“Java順序表和鏈表如何實現(xiàn)”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。