目录
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值比较,相同就删除这个节点。最后再来比较头节点。

/**
 * 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链表实例分析

在遍历链表时,将当前节点的 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

/**
 * 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链表实例分析

/**
 * 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个节点。

/*
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链表实例分析

解这个题,需要定义虚假节点来充当新链表的头节点。通过两个链表的头节点去遍历两个节点,去比较两个链表对应节点的值,将值小的节点连接到新链表的后面,知道两个链表遍历完,当其中一个链表为空时,直接将另一个链表连接到新链表后面即可。

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链表实例分析

/*
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链表实例分析

/*
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步。这样两个链表的剩余长度就相同。此时两个指针同时遍历连个链表,如果其指向一致,则两个链表相交,否则,两个链表不相交。

/**
 * 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链接】

还是快慢指针。慢指针一次走一步,快指针一次走两步。两个指针从链表起始位置开始运行。如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。

/**
 * 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链表实例分析

/**
 * 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

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 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 中的完美数 Java 中的完美数 Aug 30, 2024 pm 04:28 PM

Java 完美数指南。这里我们讨论定义,如何在 Java 中检查完美数?,示例和代码实现。

Java 中的随机数生成器 Java 中的随机数生成器 Aug 30, 2024 pm 04:27 PM

Java 随机数生成器指南。在这里,我们通过示例讨论 Java 中的函数,并通过示例讨论两个不同的生成器。

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

Java 版 Weka 指南。这里我们通过示例讨论简介、如何使用weka java、平台类型和优点。

Java 中的阿姆斯特朗数 Java 中的阿姆斯特朗数 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯特朗数指南。这里我们讨论一下java中阿姆斯特朗数的介绍以及一些代码。

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

Java 史密斯数指南。这里我们讨论定义,如何在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引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处

See all articles