服务器之家：专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - 关于 Java 的数据结构链表

关于 Java 的数据结构链表

2021-12-21 13:40吞吞吐吐大魔王 Java教程

这篇文章主要介绍了关于 Java 的数据结构链表的相关资料,需要的朋友可以参考下面文章内容

数据结构关于 Java 的链表

1. 删除链表中等于给定值 val 的所有节点

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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){
                cur=cur.next;
                prev.next=cur;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }
}

2. 反转一个单链表

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode cur=head;
        ListNode newHead=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=newHead;
            newHead=cur;
            cur=curNext;
        }
        return newHead;    
    }
}

方法： 头插法（从第二个节点开始对第一个节点进行头插）

注意：

  • 逆置不是只将数值反转，而是将节点本身进行逆置
  • 如果用前一章的 diplay 方法将逆置后的打印结果不正确，因为该 diplay 方法是从一开始定义的 head 节点开始打印，而现在真正的头节点已经改变，可以将其修改一下
?
1
2
3
4
5
6
7
8
public void display2(Node newHead){
    Node cur = newHead;
    while(cur!=null){
        System.out.print(cur.val + " ");
        cur=cur.next;
    }
    System.out.println();
}

3. 给定一个带有头结点 head 的非空单链表

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

方法一：通过遍历找到节点数，然后找到中间节点

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        count=count/2+1;
        ListNode node=head;
        int i=0;
        while(i!=count-1){
            node=node.next;
            i++;
        }
        return node;
    }
}

方法二： 快慢指针法（快指针一次走两步，慢指针一次走一步）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode middleNode(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;
        }
        return slow;
    }
}

4. 输入一个链表，输出该链表中倒数第k个结点

方法一：通过遍历找到节点数，然后找到倒数第 k 个节点

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null){
            return null;
        }
        ListNode cur = head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        if(k<1 || k>count){
            return null;
        }
        ListNode node = head;
        int i=0;
        while(i!=count-k){
            node=node.next;
            i++;
        }
        return node;
    }
}

方法二： 快慢指针法（先让快指针走 k-1 步，再让快慢指针同时走）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k<=0){
            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;
    }
}

5. 有序链表合并为一

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

?
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
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null && l2==null){
            return null;
        }
        if(l1==null && l2!=null){
            return l2;
        }
        if(l2==null && l1!=null){
            return l1;
        }
        ListNode node=new ListNode();
        ListNode head=node;
        while(l1!=null && l2!=null){
            while(l1!=null && l2!=null && l1.val<=l2.val){
                node.next=l1;
                node=node.next;
                l1=l1.next;
            }
            while(l1!=null && l2!=null && l1.val>l2.val){
                node.next=l2;
                node=node.next;
                l2=l2.next;
            }
        }
        if(l1!=null){
            node.next=l1;  
        }
        if(l2!=null){
            node.next=l2;
        }
        return head.next;
    }
}

6. 编写代码

以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

?
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
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        ListNode cur=pHead;
        ListNode as=null;
        ListNode ae=null;
        ListNode bs=null;
        ListNode be=null;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=bs;
                }else{
                    be.next=cur;
                    be=be.next;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=as;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=as;
        if(as!=null){
            ae.next=null;
        }
        return bs;
    }
}

其中 bs、be、as、ae，分别为小于 x 和大于 x 的两端的头尾节点

7. 删除该链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针

?
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
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null){
            return null;
        }
        ListNode node=new ListNode(0);
        ListNode newHead=node;
        ListNode cur=pHead;
        
        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{
                newHead.next=cur;
                newHead=newHead.next;
                cur=cur.next;
            }
        }
        newHead.next=null;
        return node.next;
    }
}

8. 链表的回文结构

?
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
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return true;
        }
        if(A.next==null){
            return true;
        }
        ListNode left=A;
        ListNode mid=A;
        ListNode right=A;
        while(right!=null && right.next!=null){
            right=right.next.next;
            mid=mid.next;
        }
        ListNode cur=mid.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=mid;
            mid=cur;
            cur=curNext;
        }
        while(mid!=left){
            if(mid.val!=left.val){
                return false;
            }
            if(left.next==mid){
                return true;
            }
            mid=mid.next;
            left=left.next;
        }
        return true;
    }
}

方法：

  • 找中间节点
  • 反转中间节点之后的链表
  • 将反转链表头尾进行比较

9. 输入两个链表，找出它们的第一个公共结点

?
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
public class Solution {
    public int getLength(ListNode head){
        if(head==null){
            return 0;
        }
        int count=0;
        while(head!=null){
            count++;
            head=head.next;
        }
        return count;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null){
            return null;
        }
        ListNode cur1=headA;
        ListNode cur2=headB;
        int length1=getLength(headA);
        int length2=getLength(headB);
        int i=0;
        if(length1>=length2){
            while(i!=length1-length2){
                cur1=cur1.next;
                i++;
            }
        }else{
            while(i!=length2-length1){
                cur2=cur2.next;
                i++;
            }
        }
        while(cur1!=cur2){
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return cur1;
    }
}

方法： 因为共同节点之后，两个链表的节点一样长。只要在共同节点之前，让两个链表移动的节点与公共节点距离相等，再一步一步移动即可

10. 给定一个链表，判断链表中是否有环

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        if(head.next==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;
    }
}

方法： 快慢指针法（通过快指针追击慢指针，能追得上则有环）

11. 给定一个链表

 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==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;
    }

重点： 上述题中 fast=head ，以及后面代码含义就是找到公共节点之后，从该链表的头节点，以及交点，一起一步一步移动，当两个节点相遇时，则为第一个公共节点

分析： 上述重点不懂点可以结合下图分析理解

 关于 Java 的数据结构链表

  • 当第一圈就追上时： 结论为 X=Y，所以两个节点每次移动一步就可
  • 当第 n 圈就追上时： 结论为 X=Y+(n-1)C。因为两个节点移动路程是一样的，并且交点那个节点移动 n-1 圈后，再要走 Y 正好到了起始节点。所以两个节点每次移动一步就可

到此这篇关于数据结构关于 Java 的链表详情的文章就介绍到这了,更多相关数据结构关于 Java 的链表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

关于 Java 的数据结构链表

原文链接：https://blog.csdn.net/weixin_51367845/article/details/120109059

  • Java
  • 链表
  • 数据结构

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    501 　 406 　 415 　 2000 　 1433 　 401 　 330 　 htmlparser 　 选择排序法 　 随机抽取 　 内存卡 　 下载器 　 十六进制字符 　 响应 　 静态工厂 　 构造函数 　 swt 　 Overview 　 对象池模式 　 子线程 　 支票 　 金额大写转换 　 空心菱形 　 AspectJ 　 面向切面编程 　 方法名 　 网址信息 　 动态代理模式 　 线程安全 　 MockBean 　
    © 2019-2021 服务器之家(www.zzvips.com) 版权所有关于我们联系我们版权申明网站地图