目錄
1、刪除值為val的所有節點
2、反轉鍊錶
3、返回鍊錶中間節點
4、傳回鍊錶第K個節點
5、合併有序鍊錶
6、以值分割鍊錶
7、判讀回文鍊錶
8、找兩個鍊錶的公共節點
9、判斷成環鍊錶
10、返回成環鍊錶的入口
首頁 Java java教程 Java鍊錶實例分析

Java鍊錶實例分析

Apr 20, 2023 pm 05:58 PM
java

1、刪除值為val的所有節點

刪除鍊錶中等於給定值val的所有節點。 【OJ連結】

定義兩個指標prev、cur,cur指向頭節點的下一個節點,prev總是指向cur的前一個結點(方便刪除節點)。透過cur指標去遍歷鍊錶,和val值比較,相同就刪除這個節點。最後再來比較頭節點。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        if(head==null){

            return null;

        }

        ListNode prev=head;

        ListNode cur=head.next;

        while(cur!=null){

            if(cur.val==val){

                prev.next=cur.next;

                cur=cur.next;

            }else{

                prev=cur;

                cur=cur.next;

            }

        }

        if(head.val==val){

            head=head.next;

        }

        return head;

    }

}

登入後複製

2、反轉鍊錶

反轉一個鍊錶。 【OJ連結】

Java鍊錶實例分析

在遍歷鍊錶時,將目前節點的 指標改為指向前一個節點。由於節點沒有引用其前一個節點,因此必須事先儲存其前一個節點。在更改引用之前,還需要儲存後一個節點。最後返回新的頭引用。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode reverseList(ListNode head) {

        if(head==null){

            return null;

        }

        ListNode cur=head.next;

        head.next=null;

        while(cur!=null){

            ListNode curNext=cur.next;

            cur.next=head;

            head=cur;

            cur=curNext;

        }

        return head;

    }

}

登入後複製

3、返回鍊錶中間節點

給定一個帶有頭節點的非空單鍊錶,傳回鍊錶的中間節點。如果有兩個中間節點,則傳回第二個中間節點。 【OJ連結】

我們可以定義兩個快慢指標(fast、slow),都指向頭節點。快指針每次走兩步,慢指針每次走一步。鍊錶有偶數個節點時,fast=null時slow為中間節點;鍊錶有奇數個節點時,fast.next=null時slow為中間節點。

Java鍊錶實例分析

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode middleNode(ListNode head) {

        if(head==null){

            return null;

        }

        ListNode slow=head;

        ListNode fast=head;

        while(fast!=null&&fast.next!=null){

            fast=fast.next.next;

            slow=slow.next;

        }

        return slow;

    }

}

登入後複製

4、傳回鍊錶第K個節點

#輸入一個鍊錶,回傳該鍊錶中倒數第K個節點。 【OJ連結】

這個題和找中間節點的想法相似。定義兩個指標(fast、slow)。在K合理的前提下,我們可以讓快指標先走K-1步,然後快慢指標同時向後走,當fast到達鍊錶結尾時,slow就指向倒數第K個節點。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

/*

public class ListNode {

    int val;

    ListNode next = null;

    ListNode(int val) {

        this.val = val;

    }

}*/

public class Solution {

    public ListNode FindKthToTail(ListNode head,int k) {

        if(k<=0||head==null){

            return null;

        }

        ListNode fast=head;

        ListNode slow=head;

        while(k-1>0){

            if(fast.next==null){

                return null;

            }

            fast=fast.next;

            //先让快节点走k-1步

            k--;

        }

        while(fast.next!=null){

            fast=fast.next;

            slow=slow.next;

        }

        return slow;

        

    }

}

登入後複製

5、合併有序鍊錶

將兩個有序鍊錶合併為一個有序鍊錶並傳回。新鍊錶是透過拼接給定的兩個鍊錶的所有節點組成的。 【OJ連結】

Java鍊錶實例分析

解這個題,需要定義假節點來充當新鍊錶的頭節點。透過兩個鍊錶的頭節點去遍歷兩個節點,去比較兩個鍊錶對應節點的值,將值小的節點連接到新鍊錶的後面,知道兩個鍊錶遍歷完,當其中一個鍊錶為空時,直接將另一個鍊錶連接到新鍊錶後面即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1==null){

            return list2;

        }

        if(list2==null){

            return list1;

        }

        //创建虚拟节点,充当新链表的头节点,值不代表任何意义

        ListNode node=new ListNode(-1);

        ListNode cur=node;

        while(list1!=null&&list2!=null){

            if(list1.val<list2.val){

                cur.next=list1;

                list1=list1.next;

            }else{

                cur.next=list2;

                list2=list2.next;

            }

            cur=cur.next;

        }

        if(list1==null){

            cur.next=list2;

        }else{

            cur.next=list1;

        }

        return node.next;

    }

}

登入後複製

6、以值分割鍊錶

將一個鍊錶依照給定值X分成兩個部分,所有小於X的節點排在大於或等於X的節點之前。不改變節點原來的順序。 【OJ連結】

首先我們需要定義四個指標(bs、be、as、ae)分別表示小於X部分鍊錶的頭節點和尾節點、大於X部分鍊錶的頭節點和尾節點。透過頭節點遍歷鍊錶,將鍊錶分為兩部分。最後將兩個鍊錶連接起來即可。需要特別注意,當小於X部分鍊錶不為空時,我們需要手動將ae.next置為空。

Java鍊錶實例分析

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

/*

public class ListNode {

    int val;

    ListNode next = null;

    ListNode(int val) {

        this.val = val;

    }

}*/

public class Partition {

    public ListNode partition(ListNode pHead, int x) {

        if(pHead==null){

            return null;

        }

        ListNode bs=null;

        ListNode be=null;

        ListNode as=null;

        ListNode ae=null;

        ListNode cur=pHead;

        while(cur!=null){

            if(cur.val<x){

                if(bs==null){

                    bs=cur;

                    be=cur;

                }else{

                    be.next=cur;

                    be=cur;

                }

            }else{

                if(as==null){

                    as=cur;

                    ae=cur;

                }else{

                    ae.next=cur;

                    ae=cur;

                }

            }

            cur=cur.next;

        }

        if(bs==null){

            return as;

            //如果小于X部分为空,则直接返回大于X部分即可。此时ae.next一定为null

        }

        be.next=as;//否则连接小于X和大于X部分

        if(as!=null){

           ae.next=null;

           //当小于X部分不为空时,ae.next可能不为null,需要手动置为null

        }

        return bs;

    }

}

登入後複製

7、判讀回文鍊錶

#判斷鍊錶是不是回文鍊錶。 【OJ連結】

首先我們需要找到鍊錶的中間節點,然後將後半段鍊錶反轉。最後透過兩邊逐步比較即可。特別注意,當鍊錶結點個數為偶數時,因為中間節點的緣故,兩邊遍歷時,無法相遇,需要特殊處理。

Java鍊錶實例分析

Java鍊錶實例分析

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

/*

public class ListNode {

    int val;

    ListNode next = null;

    ListNode(int val) {

        this.val = val;

    }

}*/

public class PalindromeList {

    public boolean chkPalindrome(ListNode A) {

        if(A==null){

            return false;

        }

        if(A.next==null){

            return true;

        }

        //求链表的中间节点

        ListNode slow=A;

        ListNode fast=A;

        while(fast!=null&&fast.next!=null){

            fast=fast.next.next;

            slow=slow.next;

        }

        //反转后半段链表

        ListNode cur=slow.next;

        while(cur!=null){

            ListNode curNext=cur.next;

            cur.next=slow;

            slow=cur;

            cur=curNext;

        }

        //判断回文链表

        while(slow!=A){

            if(slow.val!=A.val){

              return false;

           }

            if(A.next==slow){

                return true;

            }

            slow=slow.next;

            A=A.next;

        }

        return true;

    }

}

登入後複製

8、找兩個鍊錶的公共節點

輸入兩個鍊錶,輸出兩個鍊錶的第一個公共節點。沒有回傳NULL。 【OJ連結】

兩個鍊錶相交呈現Y字型。那麼兩個鍊錶長度的差肯定是未相交前兩個鍊錶節點的差。我們需要求出兩個鍊錶的長度。定義兩個指標(pl、ps),讓pl指向長的鍊錶,ps指向短的鍊錶。求兩個鍊錶的長度差len。讓pl想走len步。這樣兩個鍊錶的剩餘長度就相同。此時兩個指標同時遍歷連個鍊錶,如果其指向一致,則兩個鍊錶相交,否則,兩個鍊錶不相交。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    //求链表长度

    public int len(ListNode head){

        int len=0;

        while(head!=null){

            head=head.next;

            len++;

        }

        return len;

    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if(headA==null||headB==null){

            return null;

        }

        ListNode pl=headA;

        ListNode ps=headB;

        int lenA=len(headA);

        int lenB=len(headB);

        int len=lenA-lenB;

        if(len<0){

            //pl指向长的链表,ps指向短的链表

            pl=headB;

            ps=headA;

            len=-len;

        }

        while(len--!=0){

            pl=pl.next;

        }

        while(pl!=null){

            if(pl==ps){

                return pl;

            }

            pl=pl.next;

            ps=ps.next;

        }

        return null;

    }

}

登入後複製

9、判斷成環鍊錶

判斷鍊錶中是否有環。 【OJ連結】

還是快慢指標。慢指針一次走一步,快指針一次走兩步。兩個指標從鍊錶起始位置開始運作。如果鍊錶帶環則一定會在環中相遇,否則快指針率先走到鍊錶的末端。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        if(head==null||head.next==null){

            return false;//链表为空或者只有一个节点时,没有环

        }

        ListNode slow=head;

        ListNode fast=head;

        while(fast!=null&&fast.next!=null){

            fast=fast.next.next;

            slow=slow.next;

            if(fast==slow){

                return true;

                //如果快慢节点可以相遇,表示链表有环

            }

        }

        return false;

    }

}

登入後複製

10、返回成環鍊錶的入口

給定一個鍊錶,判斷鍊錶是否有環並回傳入環的節點。如果沒有環,則回傳NULL。 【OJ連結】

让一个指针从链表的其实在位置开始遍历,同时另一个指针从上题中两只真相与的位置开始走,两个指针再次相遇时的位置肯定为环的入口

Java鍊錶實例分析

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    //判断链表是否有环,并返回第一次快慢节点相交的位置

    public ListNode hasCycle(ListNode head){

         if(head==null||head.next==null){

            return null;

        }

        ListNode slow=head;

        ListNode fast=head;

        while(fast!=null&&fast.next!=null){

            slow=slow.next;

            fast=fast.next.next;

            if(slow==fast){

               return slow;

            }

        }

        return null;

    }

    //当返回的结点与头节点再次相交时,为环的入口

    public ListNode detectCycle(ListNode head) {

        ListNode node=hasCycle(head);

        if(node==null){

            return null;

        }else{

            while(head!=node){

                head=head.next;

                node=node.next;

            }

        }

        return head;

    }

}

登入後複製

以上是Java鍊錶實例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱門文章

倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章

倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章標籤

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

Java 中的平方根 Java 中的平方根 Aug 30, 2024 pm 04:26 PM

Java 中的平方根

Java 中的完美數 Java 中的完美數 Aug 30, 2024 pm 04:28 PM

Java 中的完美數

Java 中的隨機數產生器 Java 中的隨機數產生器 Aug 30, 2024 pm 04:27 PM

Java 中的隨機數產生器

Java 中的阿姆斯壯數 Java 中的阿姆斯壯數 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯壯數

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java中的Weka

Java 中的史密斯數 Java 中的史密斯數 Aug 30, 2024 pm 04:28 PM

Java 中的史密斯數

Java Spring 面試題 Java Spring 面試題 Aug 30, 2024 pm 04:29 PM

Java Spring 面試題

突破或從Java 8流返回? 突破或從Java 8流返回? Feb 07, 2025 pm 12:09 PM

突破或從Java 8流返回?

See all articles