1. Toy模板网首页
  2. > Toy博客

Java LeetCode篇-深入了解关于单链表的经典解法

10月前 作者：小扳 分类：Toy博客 阅读(82) 违法举报

这篇具有很好参考价值的文章主要介绍了Java LeetCode篇-深入了解关于单链表的经典解法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

  🔥博客主页： 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍ 

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构

文章目录

        1.0 移除链表元素

        1.1 使用双指针方法

        2.0 反转链表

        2.1 递归法

        2.2 头插法

        3.0 链表中倒数第 k 个节点

        3.1 递归法

        3.2 快慢指针

        4.0 合并两个有序链表

        4.1 递归法

        4.2 尾插法

        5.0 链表的回文结构

        5.1 双指针与反转

        6.0 环形链表

        6.1 快慢指针

        7.0 相交链表

        7.1 暴力解法

        7.2 计算长度

        1.0 移除链表元素

题目：

        给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

该题的链接为：203. 移除链表元素 - 力扣（LeetCode）

        1.1 使用双指针方法

         具体思路为：先来考虑如何删除目标节点，定义两个指针，对于 fast 这个指针来说：一开始就指向 head.next 的节点，然后一步步往后走，在每一次走之前需要判断 fast.val 是否与目标值 val 相等；对于 slow 这个指针来说，一开始指向 head 节点，跟着 fast 指向节点的后面的节点，如果 fast.val == val 这个两个值相等就意味着需要删除该节点，则 slow.next = fast.next ，就删除了该节点了；如果  fast.val == val 这个两个值不相等，fast = fast.next 与 slow = slow.next 继续往后走，循环结束的条件为：fast == null 。最后直接返回头节点。

代码如下：

/**
 * 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 slow = head;
        ListNode fast = head.next;

        while(fast != null) {
            if(fast.val == val) {
                slow.next = fast.next;
                fast = slow.next;
            }else {
                fast = fast.next;
                slow = slow.next;
            }

        }   
        if(head.val == val) {
            head = head.next;
        } 
    return head;

    }
}

        需要注意的是，当遇到要删除的节点就为 head 的情况，还需要多加一个条件，如果 head.val == val 时，需要将头节点往后移，head = head.next 。这段代码需要放到循环结束之后，万万不可将这段代码加在对 head 判空后面，也就是循环之前。

解释为什么只能放在循环后面的原因：

        举个例子就好了，举例 7 -> 7 -> 7 -> 7 -> null 这一段代码，需要是要删除节点的 val 为 7，那么如果将  if(head.val == val) { head = head.next;   }  这段代码放在循环之前，得出来的最终结果是 7 -> null ，我们可以发现是没有将节点值为 7 删除完全；如果将以上的代码放在循环之后，那么最终的结果为 null，符合要求的节点被完全删除了。

        

        2.0 反转链表

题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

该题的链接为：206. 反转链表 - 力扣（LeetCode）

        2.1 递归法

        具体思路为：先考虑反转后的头节点，也就是当前的尾节点，那么这个可以通过递出到底时拿到尾节点直接返回，再通过回归过程中一层层返回出来；再来考虑将中间的各个节点的指向反转，这也不难实现，也就是在回归过程中，将当前的节点的下一个节点指向当前节点即可，需要注意的是，还需要将当前节点的指向置为 null 。

代码如下：

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head);

    }

    public ListNode reverse(ListNode p) {
        if(p == null || p.next == null) {
            return p;
        }

        ListNode ret = reverse(p.next);
        p.next.next = p;
        p.next = null;
        return ret;
    }
}

        递归结束条件有两种情况：第一种，若该链表为 null ，则没有必要继续下去了；第二种情况，当递归到 p.next == null 时，返回该节点，也就是反转后的头节点。

        2.2 头插法

        具体思路为：需要先定义两个指针，对于 n2 指针来说，一开始就指向 head.next 节点；对于 n1 指针来说，一开始就指向 head 节点。循环过程： head.next = n2.next ，需要将 n2 后面的节点被 head 头节点引用，然后再将 n2.next = n1，这个过程就是头插过程，将后面的节点插到节点的最前面，再然后重新赋值头节点 n1 = n2 ，此时，n1 就是该链表中的头节点了，最后再让 n2 = head.next 继续下去。循环结束条件为：n2 == null 时，结束循环。返回头节点 n1 。

代码如下：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;

        }

        ListNode n1 = head;
        ListNode n2 = head.next;
        while(n2 != null) {
            head.next = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = head.next;
        }
        return n1;

    }
}

        需要注意的是：需要将 head 进行判空处理。

        3.0 链表中倒数第 k 个节点

题目：

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

示例1

输入：

1,{1,2,3,4,5}

复制返回值：

{5}

该题的链接为：链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

        3.1 递归法

        具体思路为：需要先定义两个成员变量，对于 int sum 来说，其作用就是用来计数；对于 ListNode end 来说，记录找到的节点。该递归不需要返回值，只要 p.next != null 时，就一直递出下去，一旦 p.next == null 时，回归过程中需要先 sum++ ，再来判断 sum 是否等于 k ，若两个值相等时，需要将 end 指向当前节点；无论该两个值相不相等，需要一直回归下去。

代码如下：

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    private ListNode end;
    private int sum ;
    public ListNode FindKthToTail(ListNode head,int k) {
        end = null;
         sum = 0;
        if(head == null) {
            return null;
        }
        recursion(head,k);
        return end;
       

    }

    public void recursion(ListNode p, int k) {
        if(p.next != null) {
            recursion(p.next, k);
        }
        sum++;
        if(sum == k) {
            end = p;
        }
    }

}

         注意的是：需要进行对 head 判空处理。

        3.2 快慢指针

        具体思路：对于 fast 指针来说，一开始的时候，指向 head ；对于 slow 指针来说，一开始的时候，指向 head ；先让 fast 先走 k 步，再跟 slow 一起走，直到 fast == null 时，当前的 slow 则为目标的节点，倒数第 k 个节点。

代码如下：

import java.util.*;
/*
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(head == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;
        
        int count = 0;
        while(count < k) {
            if(fast == null) {
                return null;
            }
            fast = fast.next;
            count++;
        }

        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;


    }
}

        需要注意的是：1.需要先对 head 进行判空处理；2. 在 fast 走 k 步的过程中，有可能会越界，所以要加上判断。

        4.0 合并两个有序链表

题目：

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

示例 1：

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

该题的链接为：21. 合并两个有序链表 - 力扣（LeetCode）

        4.1 递归法

        具体思路为：先来考虑递出的过程中，判断 l1.val 与 l2.val 的大小，若 l1.val < l2.val 时，需要将 l1 移到下一个节点；若 l2.val <= l1.val 时，需要将 l2 移到下一个节点。再来考虑回归过程，当任意一个链表为 null 时，就返回另一条不为 null 的链表，需要用当前的节点来接收。

代码如下：

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }

        if(list1.val > list2.val) {
            list2.next = mergeTwoLists( list1,list2.next);
            return list2; 
        }else {
            list1.next = mergeTwoLists( list1.next, list2);
            return list1;
        }

    }

}

        4.2 尾插法

        具体思路为：先定义出 ListNode newHead = new ListNode()；称为哨兵节点，也就是傀儡节点，再定义一个 ListNode  p  = newHead 临时变量一开始的时候指向哨兵节点。接着，让两个链表中的一个个节点分别进行对比，若 l1.val < l2.val 时，p.next = l1 ，就需要将 p.next 指向 val 较小的节点，然后 l1 = l1.next ，l1 往后移一步，再跟 l2 中的节点进行比较，最后还要让 p = p.next 往后移一步，以此类推下去。直到任意一条的链表为 null 时，p.next 指向不为 null 的链表。

代码如下：

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHand = new ListNode();
        ListNode p = newHand;

        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                p.next = list1;
                list1 = list1.next;
                p = p.next;
            }else {
                p.next = list2;
                list2 = list2.next;
                p = p.next;
            }
        }

        if(list1 != null) {
            p.next = list1;
        }
        if(list2 != null) {
            p.next = list2;
        }

        return newHand.next;

    }
}

        需要注意的是，返回傀儡节点的下一个节点，即头节点。

        5.0 链表的回文结构

题目：        

        对于一个链表，请设计一个时间复杂度为 O(n) ,额外空间复杂度为 O(1) 的算法，判断其是否为回文结构。

给定一个链表的头指针 A，请返回一个 bool 值，代表其是否为回文结构。保证链表长度小于等于 900。

测试样例：

1->2->2->1
返回：true

该题的链接为：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

        5.1 双指针与反转

        具体思路为：通过双指针这个算法来找到中间节点，再将中间节点开始的链表进行反转，最后进行遍历比较每一个节点是否相等。

        对判断回文链表更加详细的介绍点击一下链接：Java 算法篇-链表的经典算法：判断回文链表、判断环链表与寻找环入口节点(“龟兔赛跑“算法实现)-CSDN博客

代码如下：

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        ListNode slow = A;
        ListNode fast = A;
        ListNode p = A;

        //找中间节点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //然后进行反转
        ListNode pp = recursion(slow);
        while(pp != null) {
            if(pp.val != p.val) {
                return false;
            }
            pp = pp.next;
            p = p.next;
        }
        return true;
    }

    public ListNode recursion(ListNode p) {
        if(p.next == null || p == null) {
            return p;
        }

        ListNode last = recursion(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }
}

        6.0 环形链表

题目：

        给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

该题的链接为：141. 环形链表 - 力扣（LeetCode）

        6.1 快慢指针

        具体思路为：定义两个指针，每一个指针的每一次走的步数都不一样，然后一直循环下去，判断 p == null 就停止循环，否则一直下去，那么一直下去就说明有环，所以无论如何，该两个指针总会有相遇的时候。

        对判断回文链表更加详细的介绍点击一下链接：Java 算法篇-链表的经典算法：判断回文链表、判断环链表与寻找环入口节点(“龟兔赛跑“算法实现)-CSDN博客

代码如下：

/**
 * 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) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            if(slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return false;
    }
}

        7.0 相交链表

题目：

        给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

该题的链接为：160. 相交链表 - 力扣（LeetCode）

        7.1 暴力解法

        具体思路为：直接去通过遍历来寻找 A 链表中的节点是否在 B 链表中，若找到了，则返回该节点；若没找到，说明该两条链表不相交，返回 null 。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        

        while( p != null ) {
            ListNode q = headB;
            while(q != null) {  
                if(q == p) {
                    return p;
                }
                q = q.next;
            }
            p = p.next;
        }
        return null;
    }
}

       7.2 计算长度

        具体思路为：我们可以想到，能不能把两个链表变成等长的链表呢？显然若两链表不等长，那么长的链表的前 n 个结点（n 是长链表比短链表多的结点数）显然不可能是公共结点。而剩余部分两链表是等长的，自然就可以按照顺序同步后移的方法查找公共结点。

不过，为确定两链表长度差，得先遍历两链表确定长度。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        int s1 = 0;
        int s2 = 0;

        while(p != null) {
            s1++;
            p = p.next;
        }
        while(q != null) {
            s2++;
            q = q.next;
        }

        p = headA;
        q = headB;

        while(s1 < s2) {
            q = q.next;
            s2--;
        }
        while(s2 < s1) {
            p = p.next;
            s1--;
        }

        while(p != null && q != null) {
            if(p == q) {
                return q;
            }
            q = q.next;
            p = p.next;
        }
        return null;
    }    
}

Java LeetCode篇-深入了解关于单链表的经典解法,Java LeetCode篇,java,leetcode,开发语言,链表,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-755281.html

到了这里，关于Java LeetCode篇-深入了解关于单链表的经典解法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Java 算法篇-深入了解单链表的反转（实现：用 5 种方式来具体实现）

    Java 算法篇-深入了解单链表的反转（实现：用 5 种方式来具体实现）

    🔥博客主页：  小扳_-CSDN博客 ❤感谢大家点赞👍收藏⭐评论✍          文章目录         1.0 单链表的反转说明         2.0 单链表的创建         3.0 实现单链表反转的五种方法         3.1 实现单链表反转 - 循环复制（迭代法）         3.2 实现单链表反转 - 头插法

    2024年02月05日
    浏览(42)
  • Java LeetCode篇-二叉树经典解法（实现：判断平衡二叉树、找两个节点最近的祖先等）

    Java LeetCode篇-二叉树经典解法（实现：判断平衡二叉树、找两个节点最近的祖先等）

    🔥博客主页： 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 平衡二叉树         1.1 实现判断平衡二叉树的思路         1.2 代码实现判断平衡二叉树         2.0 二叉树的层序遍历         2.1 实现二叉树层序遍历的思路          2.2

    2024年02月05日
    浏览(51)
  • Java LeetCode篇-二叉搜索树经典解法（实现：二叉搜索树的最近公共祖先、根据前序遍历建树等）

    Java LeetCode篇-二叉搜索树经典解法（实现：二叉搜索树的最近公共祖先、根据前序遍历建树等）

    🔥博客主页： 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 判断合法         1.1 使用遍历方式实现验证二叉搜索树         1.2 使用递归方式实现验证二叉搜索树         2.0 求范围和         2.1 使用非递归实现二叉搜索树的范围和

    2024年02月03日
    浏览(49)
  • 深入浅出：单链表的实现和应用

    深入浅出：单链表的实现和应用

      🌱博客主页：青竹雾色间. 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注  ✨ 人生如寄，多忧何为  ✨ 目录 前言 单链表的基本概念 节点 头节点 尾节点 单链表的基本操作 创建单链表 头插法： 尾插法： 插入（增）操作  删除（删）操作： 查找（查）操作： 修改（改

    2024年02月08日
    浏览(73)
  • 【数据结构与算法】深入浅出：单链表的实现和应用

    【数据结构与算法】深入浅出：单链表的实现和应用

      🌱博客主页：青竹雾色间. 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注  ✨ 人生如寄，多忧何为  ✨ 目录 前言 单链表的基本概念 节点 头节点 尾节点 单链表的基本操作 创建单链表 头插法： 尾插法： 插入（增）操作  删除（删）操作： 查找（查）操作： 修改（改

    2024年02月08日
    浏览(75)
  • 关于链表的题目—leetcode

    关于链表的题目—leetcode

    问题描述： 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 - 1 - 9. 示例 2: 输入

    2023年04月25日
    浏览(36)
  • LeetCode | 一探环形链表的奥秘【快慢双指针妙解BAT等大厂经典算法题】

    LeetCode | 一探环形链表的奥秘【快慢双指针妙解BAT等大厂经典算法题】

    前言 本文总结了力扣141.环形链表|以及142.环形链表||这两道有关环形链表的求解方案，去求证链表是否带环已经如何找出入环口的结点。 有关环形链表，在BAT等大厂面试中均有出现，一般是属于 中等难度 的题，需掌握 原题传送门 给你一个链表的头节点 head ，判断链表中是

    2024年02月01日
    浏览(44)
  • 单链表的多语言表达：C++、Java、Python、Go、Rust

    单链表的多语言表达：C++、Java、Python、Go、Rust

    是一种链式数据结构，由一个头节点和一些指向下一个节点的指针组成。每个节点包含一个数据元素和指向下一个节点的指针。头节点没有数据，只用于表示链表的开始位置。 单链表的主要操作包括： 添加元素：在链表的头部添加新元素，需要修改头节点的指针。 删除元素

    2024年02月15日
    浏览(33)
  • JavaEE 初阶篇-深入了解单例模式（经典单例模式：饿汉模式、懒汉模式）

    JavaEE 初阶篇-深入了解单例模式（经典单例模式：饿汉模式、懒汉模式）

    🔥博客主页： 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍ 文章目录         1.0 单例模式的概述         2.0 单例模式 - 饿汉式单例         2.1 关于饿汉式单例的线程安全问题         3.0 单例模式 - 懒汉式单例         3.1 关于懒汉式单例的线程安全问题      

    2024年04月15日
    浏览(48)
  • Go-Python-Java-C-LeetCode高分解法-第八周合集

    Go-Python-Java-C-LeetCode高分解法-第八周合集

    本题解Go语言部分基于 LeetCode-Go 其他部分基于本人实践学习 个人题解GitHub连接：LeetCode-Go-Python-Java-C 欢迎订阅CSDN专栏，每日一题，和博主一起进步 LeetCode专栏 我搜集到了50道精选题，适合速成概览大部分常用算法 突破算法迷宫：精选50道-算法刷题指南 本文部分内容来自网上

    2024年02月07日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包