🔥博客主页: 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍
文章目录
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:
输入: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 。最后直接返回头节点。
代码如下:文章来源:https://www.toymoban.com/news/detail-755281.html
/** * 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:
输入: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:
输入: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:
输入: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
开始相交:题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
该题的链接为: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; } }
文章来源地址https://www.toymoban.com/news/detail-755281.html
到了这里,关于Java LeetCode篇-深入了解关于单链表的经典解法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!