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

博客主页：【小扳_-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 。最后直接返回头节点。

代码如下：

/** * 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 递归法

具体思路为：需要先定义两个成员变量，对于 intsum 来说，其作用就是用来计数；对于 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 hereListNode 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;}}