对于链表，笔者在之前就已经有过几篇文章，详细的讲解了！感兴趣的各位老铁，请进入博主的主页进行查找！
https://blog.csdn.net/weixin_64308540/?type=blog
言归正传！对于链表，光学不做，也是白搭！所以，今日来几道小小的练习题顺顺手吧！！
温馨小提示一下：该题为数据结构的题目！必须画图！请大家思考时候也在画图！！
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
其实刚看见这个题目的时候，笔者也是一脸懵逼！但是，后来想了想，用头插法是一个不错的选择，相信各位老铁也可以想出来更好的办法的！
下面请看笔者用头插法书写的简单代码：
public ListNode reverseList( ListNode head){ if (head == null){ return null; //说明一个节点都没有 } if (head.next == null){ return null;//说明只有一个节点 } ListNode cur = head.next;//先记录头节点后的第一个节点 head.next =null; while (cur !=null){ ListNode curNext =cur.next; //一定要有 //头插法，插入cur cur.next =head; head=cur; cur=curNext; } return head; }
876. 链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
- 给定链表的结点数介于 1 和 100 之间。
显而易见，该题可以用快慢指针来进行！！需要保持的是：快到速度是慢的速度的2倍！！
思路：同时在head位置出发，fast的速度是slow的速度的2倍，路程相同，所以，在fast在终点的时候，slow在中间位置
分析：当节点为奇数的情况下：
fast与slow第一次往后走时：
再次往后走时候：
此时fast.next==null，再往后走的话就会进行空指针异常了！所以，这个算是一个判断的条件吧！
当节点为偶数的情况下：
fast与slow第一次往后走时：
再次往后走时候：
此时fast==null，再往后走的话就会进行空指针异常了！所以，这个算是第二个判断的条件吧！
因此，经过上述两个条件的分析，我们可以有：循环结束的情况：fast==null ||fast.next==null这两个条件！
经过分析，我们可以得出，fast !=null && fast.next !=null，而且这两个条件的先后顺序不能互换！！原因在于：当fast为null的时候，进行fast.next != null的判断会造成空指针异常！
因此，我们有着一下的代码：
public ListNode middleNode(ListNode head){ ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow;//循环结束的时候，此时slow正好在中间节点！ }
或许有着老铁会有小小的疑惑！当只有一个节点的时候，是如何判断的？？或许大家忘了：当只有一个节点的时候,此时，fast.next == null，则不会进入循环！！
链表中倒数第k个结点
描述
输入一个链表，输出该链表中倒数第k个结点。
示例1
输入：
1,{1,2,3,4,5}
返回值：
{5}
若是我们要求：仅仅遍历一遍链表，就能得出出后的倒数第K个节点，不知道你会怎么思考？？
思路：快慢指针！！
如下图所示：
此时fast为最后一个节点，slow为倒数第三个节点，slow距fast需要走2步！！因此，想要倒数第K个节点，我们可以：
- 先让fast走K-1步（或者fast先走K步，此时，判断条件就变为fast为null）
- fast走完K-1步之后，fast和slow开始一步一步往后走
- 当fast.next为null 的时候，slow所指的位置就是倒数第K个节点！
经过上述的分析，我们有着一下的代码：
//链表的倒数第k个节点 public ListNode FindKthToTail(ListNode head,int k) { //判断是否合法 if (k<=0 || head == null){ return null; } ListNode fast =head; ListNode slow =head; //让fast先走k-1步 while (k-1 !=0){ fast =fast.next; if (fast == null){ return null; } k--; } //fast和slow一块一步一步走 while (fast.next != null){ fast =fast.next; slow =slow.next; } return slow; }
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列
这个思路理解起来有点儿难度！表达不怎么样！笔者仅仅提供自己的思路吧！
这个解题便是笔者的思路！尴尬
下面请看代码：
//合并两个有序链表 public ListNode mergeTwoLists(ListNode head1 , ListNode head2){ ListNode newhead =new ListNode();//实列化一个虚拟的节点 ListNode tmp =newhead; //当两个链表都有数据的时候 while (head1 !=null && head2 != null){ if (head1.val < head2.val){ tmp.next=head1; head1=head1.next; tmp=tmp.next; }else { tmp.next=head2; head2=head2.next; tmp=tmp.next; } } //当只有一个链表有数据的时候 if (head1 !=null){ tmp.next =head1; } if (head2 !=null){ tmp.next =head2; } return newhead.next; }
OR36 链表的回文结构
描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
思路：对于该题目，我们可以先找到中间位置，然后再将中间位置往后的进行反转一下！！
因此，我们有着下列的简单代码：
public boolean chkPalindrome(ListNode head) { if (head ==null){ return false; } if(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; //代表当前需要反转的节点 while (cur !=null){ ListNode curNext =cur.next; cur.next =slow; slow=cur; cur=curNext; } //一个从前往后，一个从后往前 while (slow !=head){ if (head.val !=slow.val){ return false; } //偶数的情况 if (head.next ==slow){ return true; } slow=slow.next;//从后往前 head=head.next;//从前往后 } return true; }
对于这个题目，想必最难的地方在于，找到中间节点之后的翻转！！这个感觉有点儿难度！其他的想必都是很简单的思路了吧！！
CM11 链表分割
描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
在这个题目中，我们需要注意的是，x可能是链表里面的数据，也可能不是链表里面的数据！另外：原链表的最后一个节点所存储的数据跟x比的大小？？（需不需要置null问题）
在下列的讲述中，假设x的值为15！
情况1：假设初始状态下的链表数据为：（链表的最后一个节点所存储的数据小于x的值）
经过链表分割之后：
情况2：假设初始状态下的链表数据为：（链表的最后一个节点所存储的数据大于x的值）
经过链表分割之后：
那么，问题来了，怎么将小于x的节点放在前面，并且还能保证顺序不变呢？？
思路：假设有2段，第一段放<x的节点，第2段放>=x的节点，最后再将这2段串起来，不就可以了蛮？？
因此，对于该用列：
我们有着：
因此，在这个思路中，我们只需要维护各个节点的next便可以了！！
在这个过程中，用到的还是原来的节点，没有实列化新的节点，所以，还是链表本身的修改！！不要忘记，将最后一个节点置为null！！
下面请看笔者的简单代码：
public ListNode partition(ListNode head,int x){ ListNode bs=null; ListNode be=null; //bs be用来记录<x的节点 ListNode as=null; ListNode ae=null; //as ae用来记录>=x的节点 ListNode cur =head;//滴滴代跑 while (cur !=null){//循环的总条件 if(cur.val<x){ if (bs==null){ //判断是否为第一次插入 bs=cur;//确保bs在头节点保持不动 be=cur; }else { be.next=cur; //尾插法插入节点 be=be.next; } }else { if (as==null){ as=cur;//确保as在头节点保持不动 ae=cur; }else { ae.next=cur; ae=ae.next; } } cur=cur.next; //在上述的if……else语句中，都用到了该语句，所以可以提取出来！ } //有可能不会同时存在即大于又小于x的数据！（即一边倒的情况） if (bs==null){ return as; } //没有经过上述的if(be==null）语句，就说明，第一段不为空 be.next=as; //此时第一段不为空 if (as!=null){ ae.next=null; //如果第二段不为空，则将最后的一个节点置为空 } return bs; }
经过该列题，我们可以看出来：与链表相关的练习题很难！很难，但是我们要想成功的做出来，一定要学会思考，学会画图解决！
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
- intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
- listA - 第一个链表
- listB - 第二个链表
- skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
- skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
- listA 中节点数目为 m
- listB 中节点数目为 n
- 1 <= m, n <= 3 * 104
- 1 <= Node.val <= 105
- 0 <= skipA <= m
- 0 <= skipB <= n
- 如果 listA 和 listB 没有交点，intersectVal 为 0
- 如果 listA 和 listB 有交 点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
解题思路：先求出两个节点的长度，在球场两个节点的长度的差值（长度的差值体现在—》在节点相交之前的部分）若差值为0，则两个节点一块走，相遇的时候为相交的节点，若差值不为0，则长的节点先走差值个长度的步数，然后在一块走，相遇的时候为相交的节点！！
那么问题来了：
- 你知道哪个链表长吗？？
- 你怎么判断相遇？？是用headA==headB吗？？但是，需要注意的是：当headA==headB==null的情况！走完了都不一定相交！
经过上述的分析，我们有着以下的代码：
public ListNode getIntersectionNode(ListNode headA , ListNode headB){ //分别求出两个链表的长度 int lenA=0; int lenB=0; ListNode pl=headA;//假设pl对应的为长链表 ListNode ps=headB;//假设ps对应的为短链表 while (pl !=null){ lenA++; pl=pl.next; } while (ps !=null){ lenB++; ps=ps.next; } //求出长度以后，此时pl和ps此时都指向null，所以要指回来 pl=headA; ps=headB; //通过len的正负，可以判断两个链表的长度 int len=lenA-lenB; //根据len的正负，来修改指向 if (len<0){ pl=headB;//确保pl指向的为长链表 ps=headA;//确保ps指向的为短链表 len=lenB-lenA; } //此时，len一定是个正数！ //pl指向的为长链表 并且 ps指向的为短链表 //让长链表先走len步 while (len !=0){ pl=pl.next; len--; }//出while循环的时候，长链表与短链表距离相交的或者null有着相同的距离 while (pl != ps){ pl=pl.next; ps=ps.next; }//此时pl与ps要么相交，要么都为null return pl; }
思路很重要哟！！加油
