文章目录

• 前言
• 一 删除链表中等于给定值“val”的所有节点
• 二 反转一个单链表
• 三 求中间节点
• 四 链表倒数第K个节点
• 五 合并有序链表
• 六 链表分割
• • 注意细节：
• 七 删除重复结点
• 八 链表的回文结构
• 九 相交链表
• 十 判断表中是否有环
• 十一 环形链表II
• OJ题目网址

前言

本篇文章主要就是讲述数据结构中链表有关的一些经典的OJ题，文末也给大家提供了OJ题的具体网址供大家练习，通过这些OJ题希望对你理解链表有一个更深层次的理解，最后创作不易，希望大家能够给予鼓励，点点赞，评论交流学习！

一 删除链表中等于给定值“val”的所有节点

例如：
输入：head = [1,2,6,3,6], val = 6
输出：[1,2,3]

图解过程：

删除之后

思路有了之后，代码如下：

public nodelist deletion(int val){if (head==null)return null;nodelist cur=head;while (cur!=null){while(cur.next!=null&&cur.next.val==val){cur.next=cur.next.next;}cur=cur.next;}if(head.val==val){head=head.next;}return head;}

二 反转一个单链表

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

代码具体实现

public nodelist fanzhuang(){nodelist prve=null;nodelist cur=head.next;while (cur!=null){head.next=prve;prve=head;head=cur;cur=cur.next;}head.next=prve;return head;}

三 求中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
例如：
head=[1,2,3,4,5] 返回3
head=[1,2,3,4] 返回3

图解分析

代码实现：

//中间节点问题//解决方法快慢指针public nodelist midnode(){nodelist fast=head;nodelist slow=head;while (fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}

对于两个节点的分析方法可以自己画图体会，就能更好的理解这个题目。在这里我们提出一个变式，如果有两个节点，我们要求要返回第一个节点该怎么做？
具体的代码实现如下：

public nodelist midnode(){nodelist fast=head;nodelist slow=head;while (fast!=null&&fast.next!=null){fast=fast.next.next;if (fast==null){return slow;}slow=slow.next;}return slow;}

四 链表倒数第K个节点

具体代码实现：

//求倒数第k个节点public nodelist node(int k){if (k<0||head==null)return null;nodelist slow=head;nodelist fast=head;while (k-1!=0){fast=fast.next;if (fast==null){//如果超出了范围，那么fast应该是一个nullreturn null;}k--;}while (fast.next!=null){fast=fast.next;slow=slow.next;}return slow;}

五 合并有序链表

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

对于这种题目我们可以采用，创建一个新的节点，然后把他们都给串起来具体实现代码如下：

//合并有序列表public static nodelist mergeTwoLists(nodelist head, nodelist head1) {nodelist newhead=new nodelist(-1);//创建一个新的节点nodelist cur=newhead;while(head!=null&&head1!=null){if(head.val<head1.val){cur.next=head;cur=head;head=head.next;}else{cur.next=head1;cur=head1;head1=head1.next;}}if(head==null){cur.next=head1;}else{cur.next=head;}return newhead.next;}

六 链表分割

问题描述：

现有一链表的头指针 ListNode head，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

链表分割前：

分割之后：

在这里要注意的是，我们还得要先定义一个cur去遍历链表，然后再利用这四个空结点将他们串起来。这里要值得注意的是对于一开始进入的as，ae，bs，be，我们需要分开讨论。

注意细节：

1 如果x的值取的合适，对于分割的链表前半部分可能是没有数据的，也就是说as=null，那么此时我们就必须返回bs（如果后半部分也为空，那就说明就是一个空链表）
2 判断完上一个之后，我们必须要让ae.next=bs，这样才能把分割的链表链接起来
3 对于分割链表，我们不可能确保最后一个元素一定是在第二部分，也有可能是在第一部分，那么这个时候就会有一个问题，那就是这个链表没有尾巴了，所以我们要把be.next置为null
具体代码实现：

//链表的分割public static nodelist spiltist(nodelist head,int x){nodelist as=null;nodelist ae=null;nodelist bs=null;nodelist be=null;nodelist cur=head;if (head==null)return null;while (cur!=null){if (cur.val<x){//第一次进入if (as==null){as=cur;ae=cur;}else{//不是第一次进入ae.next=cur;ae=ae.next;}}else{//第一次进入if (bs==null){bs=cur;be=cur;}else{//不是第一次进入be.next=cur;be=be.next;}}cur=cur.next;}if (as==null){//判断前半部分是否会有数据return bs;}ae.next=bs;//把前后两个部分拼接起来if (bs!=null&&be.next!=null){//判断be.next是否为null，不是null，手动置为nullbe.next=null;}return as;}

七 删除重复结点

问题描述：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

删除前：

删除后：

通过以上两张图片，我们可以利用一个傀儡结点，去把那些不重复的节点给串起来，然后返回new.next就会是我们要得到的链表。
注意细节：
1 不能一眼认定，newhead.next就是head，这是不对的，因为如果一个链表为{1，1，2，3}，就可以说明这个错误的观点
2 对于傀儡结点与链表直接的联系，我们可以通过定义一个temp，让temp=newhead，当cur.val!=cur.next.val的时候，让temp.next=cur
具体代码实现如下：

//删除重复的结点public nodelist delet(){nodelist newhead=new nodelist(1);nodelist cur=head;nodelist temp=newhead;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{temp.next=cur;cur=cur.next;temp=temp.next;}}if(temp.next!=null){temp.next=null;}return newhead.next;}

这里要特别提一下最后的if语句，在这个代码中，如果链表为{1，2，3，3，3}，如果没有if语句那么最后重复的节点是删不去的，根据上面代码，我们要得到的就是当cur=null的时候，temp.next=null,所以在这里我们有必要在这里进行一个这样的判断。

八 链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构
例如：1->2->2->1
返回：true

一 需要利用快慢指针找到中点

二 反转链表

在反转链表中，我们需要定义一个cur，让cur.next=slow，这样就完成了当前slow所在的下一个节点的反转，我们还需要往下走，需要在定义一个curNext去记录cur的下一个节点，不然后一个节点就找不到了，我们在把slow=cur，这样就把slow往后移了一位，我们在令cur=curNext，curNext=curNext.next（这里的要注意要利用一个if语句判断一下，curNext是否为null），结合上述，最终的目的就是反转到最后一个节点（就是slow的位置要在最后一个节点上），那么我们反转节点肯定不止一个，所以我们是需要一个循环的，那么这个循环的终止条件就是cur！=null
三 判断回文结构
从反转之后的图片来看，如果是回文结构，那么此时我们slow与head同时往后走，那么就会有head与slow相遇。这里就要特别说一下，以上情况是针对奇数个节点展开的讨论，偶数节点其实也是一样的，只不过在判断时，变成head.next=slow，具体的图可以自己尝试去画一画。在代码中，我会把两种情况的总代码写出来。
代码展示

public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereif(head==null||head.next==null)return false;//寻找中点ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}//反转链表ListNode cur=slow.next;ListNode curNext=cur.next;while(cur!=null){cur.next=slow;slow=cur;cur=curNext;if(curNext!=null){curNext=curNext.next;}}//判断回文结构while(head!=slow){if(head.val==slow.val){head=head.next;slow=slow.next;if(head.next==slow){return true;}}else{return false;}}return true;} }

九 相交链表

题目描述

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

对于相交节点，我们同样采用快慢指针的做法，设headA=slow，headB=fast，从图中我们可以看出B比A长，那么我们就要定义一个整形，来表示B与A之间的长度之差，让fast多走这个差步，之后fast与slow一起走，之后就会相遇，我们就返回相遇的节点

对于所给的链表，也可以是这种，那么这个时候也不要紧，我们可以利用一个if在前一个的基础上来判断一下，如果B更长，我们就可以交换一下fast与slow的指向
具体实现代码如下：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode slow=headA;ListNode fast=headB;int lena = 0;int lenb = 0;while(slow!=null){lena++;slow=slow.next;}while(fast!=null){lenb++;fast=fast.next;}slow=headA;fast=headB;int c=lenb-lena;if(c<0){fast=headA;slow=headB;c=lena-lenb;}while(c!=0){fast=fast.next;c--;}while(fast!=slow){fast=fast.next;slow=slow.next;}return slow;} }

十 判断表中是否有环

对于是否成环问题，我们采用快慢指针前去解决，我们让fast一次走两步，slow一次走一步，那么slow与fast终究会相遇的，可不敢让fast走三次，如果只有两个节点，那么是永远不会相遇的
具体代码实现如下

public class Solution {public boolean hasCycle(ListNode head) {if(head==null||head.next==null)return false;ListNode fast=head.next;ListNode slow=head;while(fast!=null&&fast.next!=null){if(fast==slow){return true;}slow=slow.next;fast=fast.next.next;}return false;} }

十一 环形链表II

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

如图我们就是要返回2这个节点，对于这种题，我们也是利用快慢指针前去解决
1 先找到fast与slow的相遇点
2 令fast与slow其中一个置为头结点的位置，两个一起走，就会走到入环的第一个节点
代码实现：

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow=head;ListNode fast=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;}slow=head;while(slow!=fast){slow=slow.next;fast=fast.next;}return fast;} }

OJ题目网址

1 删除链表中等于给定值 val 的所有节点
2 反转一个单链表
3 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
4 输入一个链表，输出该链表中倒数第k个结点。
5 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
6 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
7 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
8 链表的回文结构
9 输入两个链表，找出它们的第一个公共结点。
10 给定一个链表，判断链表中是否有环
11 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

总结

以上是生活随笔为你收集整理的详解单链表经典OJ题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。