文章目录
LinKedList与链表 (2)
前言： 上文我们已经学习了无头单向不循环链表，并留下来，一些OJ题， 本文就来完成这些题目。
?
链接
?
1.移除链表元素
?
2.反转链表
?
3.链表的中间结点
?
4.链表中倒数第k个结点_
?
5.合并两个有序链表
?
6.链表分割
?
7.链表的回文结构
?
8.相交链表
?
9.环形链表
?
10.环形链表 II
这里我们的 移除 链表元素，再上文的删除操作已经完成之类就不再继续了。
?
下面我们就来开始本文的学习 
?
1.反转链表
?
翻转链表可以说是非常经典的 题目了， 想必学习了链表的都会遇见这一题，那么我们就来完成这一题
?
图一： 翻转的链表
?
图二 ：
?
图三 ：
?
代码实现 :
?
2.链表的中间结点
?
图一 ： 题目分析
?
图二 ： 解法 快慢指针 奇数情况
?
图三 ： 偶数情况
?
代码实现 :
?
这里改一下题目 ： 如果是偶数节点我们返回中间两个节点的第一个节点
?
这里可以思考一下， 其实非常简单， 这里就可以拿我们之前实现的链表来测试 。
?
思路 ： 就是当 快 指针 prev == null的时候直接跳出循环 ，不执行最后一次的 show = show.next 即可
?
图 ：
其实 这里个题目还有一种思路 就是 ，求一遍链表长度，然后 让show 走 长度的一半也能找到我们的中间节点，但是这个写法不推荐，求长度遍历一次，走的时候又会遍历一次。
这道题我们就完成了， 下面继续
?
3.链表中倒数第k个结点_
?
题 ：
在这里插入图片描述
?
思路一 ：求链表的长度， 假设我们要求倒数第2 个节点，链表长度 5， 5 - 2 等于 3 ，那么我们 cur 从头节点开始 走 3 次 就找到了我们的节点返回即可
我想肯定有很多同学能想到这种方法，但是我们需要遍历链表两次 那么我们 能不能只遍历链表一次就找到我们的节点呢 ？
这里就可以看思路二 , 上面这个方法 可以自己尝试实现一下。
?
思路二 : 同样是快慢指针，只不过不是同时走了，而是先让一个走 k - 1 步然后再一起走 ，相当于求出 总长度 减去 要求的倒数第 k 个节点 等于我们要走的步数， 快指针子走完了 k - 1 步，那么 接下来快慢指针 一起走， 当 快指针 的next 域等于 null 那么说明找到了返回慢指针即可
?
图解 ：
?
特殊情况 ： k 大于链表长度
?
代码实现：
?
注意 ： 这里并不是一定要走 k - 1 步 ，走 k 步也是可以的 ， 那么就是需要更改结束条件，
最后注意一下判断 k 是否大于 链表长度的条件就需要思考一下。
?
4.合并两个有序链表
?
看到这道题， 如果是我们写过两个有序数组合并成一个有序的数组，那么这道题就非常简单了。
一个思路 就是遍历 ，然后比较 找出两个之间的最小值然后赋值到新的链表上即可
?
图一 ：
?
图二 ：
?
代码实现 :
?
5.链表分割
?
图一：题目分析
?
图二 ：思路
?
图三 ：
?
代码实现
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
// 创建两条线 : 四个指针 头和尾
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
// 遍历链表找到 小于 x 和 大于 x 的放在对应的线中
// 创建 cur 代替 pHead 移动， 这里使用 pHead 移动也可以
ListNode cur = pHead;
//结束循环条件 cur != null
while(cur != null){
// 判断 当前的val 值
if(cur.val < x){
// 放在 bs - as 中 ， 如果是第一次存放，那么都需要引用
if(bs == null){
bs = cur;
be = cur;
// cur = cur.next ;
}else {
// 此时不是第一次放入， 让 be 移动即可
be.next = cur;
be = be.next;
// cur = cur.next;
}
}else {
// 此时 说明 val 大于 x
if(as == null){
// 第一次 存放
as = cur;
ae = cur;
// cur = cur.next;
}else {
// 不是第一次存放
ae.next = cur;
ae = ae.next;
// cur = cur.next;
}
}
// 可以看到 cur = cur.next , 不管再哪里都需要，那么就在最后写即可
cur = cur.next;
}
// 找完了 小于x 和 大于 x 放到了对应的地方，开始串联
//特殊情况 : 如果 没有小于 x的 判断一下
if(bs == null){
// 直接返回 as即可
return as;
}
// 此时说明有，那么就直接 链接
be.next = as;
// 如果没有 大于 x 的 说明 as == null
// 那么 be.next = as 相当于 be.next = null
//如果有大于x的需要手动将尾部制空 -- 示例图正好最后的节点为空， 但并不一定ae指向的在·就为空，这里就需要手动置空
if(as != null){
ae.next = null;
}
return bs;
}
}
这道题就过了，下面我们继续
?
6.链表的回文结构
?
图一：题目分析
?
图二:
?
图三:
代码实现 :
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
// write code here
// 如果只有一个节点，默认是回文的
if(head.next == null){
return true;
}
// 先找中点
ListNode show = head;
ListNode prev = head;
while(prev != null && prev.next != null){
prev = prev.next.next;
show = show.next;
}
// 此时 我们的show 就是中间节点
ListNode cur = show.next;
// 开始翻转链表
while(cur != null){
ListNode curNext = cur.next;
cur.next = show;
show = cur;
cur = curNext;
}
while(head != show) {
// 这里 head.next == show && head.val == show.val 可以省略成下面
if(head.next == show ){
// 偶数情况
return true;
}
if(head.val == show.val){
head = head.next;
show = show.next;
}else {
// 此时 head.val != show.val 说明当前不是回文
return false;
}
}
return true;
}
}
?
7.相交链表
?
图一
?
图二
?
代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int count1 = 0;
int count2 = 0;
ListNode cur1 = headA;
ListNode cur2 = headB;
while(cur1 != null){
count1++;
cur1 = cur1.next;
}
while(cur2 != null){
count2++;
cur2 = cur2.next;
}
cur1 = headA;
cur2 = headB;
if(count1 > count2){
int ret = count1 - count2;
while(ret != 0){
cur1 = cur1.next;
ret--;
}
// 让 长的链表先走 ， 走到链表长度一样
while(cur1 != null && cur2 != null){
if(cur1 == cur2){
return cur1;
}
cur1 = cur1.next;
cur2 = cur2.next;
}
}else {
int ret = count2 - count1;
while(ret != 0){
cur2 = cur2.next;
ret--;
}
while(cur1 != null && cur2 != null){
if(cur1 == cur2){
return cur1;
}
cur1 = cur1.next;
cur2 = cur2.next;
}
}
return null;
}
}
?
注意:上面重复的代码很多，所以我们可以写成方法，传参调用即可。
?
8.环形链表
?
图解 :
?
代码实现：
?
思考: 这里我们快指针每次都是 走 两步，那么我们能不能走更多步呢？
?
9.环形链表 II
?
图一：prev走一圈情况
?
图二: prev 走 多圈情况
?
代码实现
这里链表的 10道经典题目就完成了， 下面我们就可以来学习一下双向链表
下文预告 双向链表的实现