链表题解

移除链表元素

这里以链表 1 4 2 4 来举例，移除元素4。

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，

而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

也有另外的一种逻辑：可以设置一个虚拟的头结点，就可以统一操作了。

翻转指针

双指针法

伪代码：

• 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
• 然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

• 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
• 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时们return pre指针就可以了，pre指针就指向了新的头结点。

  // 双指针
  class Solution {
  public ListNode reverseList(ListNode head) {
  
      ListNode prev = null;
      ListNode cur = head;
      ListNode temp = null;
  
      while (cur != null) {
          temp = cur.next;// 保存下一个节点
          cur.next = prev;
          prev = cur;
          cur = temp;
      }
  
      return prev;
  }
  }
  

递归实现

// 递归 
class Solution {

    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }
    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        prev = cur;
        cur = temp;
        return reverse(prev, cur);
    }
}

两两交换链表中的节点

// 递归版本
class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;
        return next;
    }
} 
// 虚拟头结点
class Solution {
  public ListNode swapPairs(ListNode head) {
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode prev = dummyNode;
    while (prev.next != null && prev.next.next != null) {
      ListNode temp = head.next.next; // 缓存 next
      prev.next = head.next;          // 将 prev 的 next 改为 head 的 next
      head.next.next = head;          // 将 head.next(prev.next) 的next，指向 head
      head.next = temp;               // 将head 的 next 接上缓存的temp
      prev = head;                    // 步进1位
      head = head.next;               // 步进1位
    }
    return dummyNode.next;
  }
}

删除链表的倒数第N个节点

双指针的经典应用，

如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。

删掉slow所指向的节点就可以了。

定义fast指针和slow指针，初始值为虚拟头结点

• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）

  

• fast和slow同时移动，直到fast指向末尾

  

• 删除slow指向的下一个节点

  

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        // 记住 待删除节点slow 的上一节点
        ListNode prev = null;
        while (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        // 上一节点的next指针绕过 待删除节点slow 直接指向slow的下一节点
        prev.next = slow.next;
        // 释放 待删除节点slow 的next指针, 这句删掉也能AC
        slow.next = null;
        return dummy.next;
    }
}

链表相交

• 们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置

• 此时们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到焦点。
• 否则循环退出返回空指针。

  /**
  

• 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 curA = headA;
  ListNode curB = headB;
  int lenA = 0, lenB = 0;
  while (curA != null) { // 求链表A的长度
      lenA++;
      curA = curA.next;
  }
  while (curB != null) { // 求链表B的长度
      lenB++;
      curB = curB.next;
  }
  curA = headA;
  curB = headB;
  // 让curA为最长链表的头，lenA为其长度
  if (lenB > lenA) {
      //1. swap (lenA, lenB);
      int tmpLen = lenA;
      lenA = lenB;
      lenB = tmpLen;
      //2. swap (curA, curB);
      ListNode tmpNode = curA;
      curA = curB;
      curB = tmpNode;
  }
  // 求长度差
  int gap = lenA - lenB;
  // 让curA和curB在同一起点上（末尾位置对齐）
  while (gap-- > 0) {
      curA = curA.next;
  }
  // 遍历curA 和 curB，遇到相同则直接返回
  while (curA != null) {
      if (curA == curB) {
          return curA;
      }
      curA = curA.next;
      curB = curB.next;
  }
  return null;
  

  }

}

环形链表II 
------------------------

主要考察两知识点：
* 判断链表是否环
* 如果有环，如何找到这个环的入口

判断链表是否有环 
--------------------

可以使用快慢指针法， 分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，

如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

![](https://static.oomspot.com/image/cnbo/2020/2465789-20210910171538243-726927225.gif)

public class Solution {

public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {// 有环
            ListNode index1 = fast;
            ListNode index2 = head;
            // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;
        }
    }
    return null;
}

}

> 原文创作：ML李嘉图
>
> 原文链接：https://www.cnblogs.com/zwtblog/p/15253126.html

## 文章列表
- [项目MyBlog](https://www.oomspot.com/post/xiangmumyblog)
- [阶段总结Java基础超进阶](https://www.oomspot.com/post/jieduanzongjiejavajichuchaojinjie)
- [链表题解](https://www.oomspot.com/post/lianbiaotijie)
- [郭德纲罗翔语录](https://www.oomspot.com/post/guodegangluoxiangyulu)
- [语录转载](https://www.oomspot.com/post/yuluzhuanzai)
- [设计模式更新中](https://www.oomspot.com/post/shejimoshigengxinzhong)
- [设计模式图解](https://www.oomspot.com/post/shejimoshitujie)
- [论坛项目](https://www.oomspot.com/post/luntanxiangmu)
- [计算机网络汇总](https://www.oomspot.com/post/jisuanjiwangluohuizong)
- [计算机网络TCP篇](https://www.oomspot.com/post/jisuanjiwangluotcppian)
- [计算机网络IP篇](https://www.oomspot.com/post/jisuanjiwangluoippian)
- [计算机网络HTTP篇](https://www.oomspot.com/post/jisuanjiwangluohttppian)
- [计算机组成原理图解](https://www.oomspot.com/post/jisuanjizuchengyuanlitujie)
- [计算机组成原理初见](https://www.oomspot.com/post/jisuanjizuchengyuanlichujian)
- [自定义starter](https://www.oomspot.com/post/zidingyistarter)
- [缓存穿透，击穿，雪崩详解](https://www.oomspot.com/post/huancunchuantoujichuanxuebengxiangjie)
- [笔试格式](https://www.oomspot.com/post/bishigeshi)
- [温故知新输入网址显示网页到底到底到底到底发生了什么？](https://www.oomspot.com/post/wenguzhixinshuruwangzhixianshiwangyedaodidaodidaod)
- [深度学习之神经网络的结构](https://www.oomspot.com/post/shenduxuexizhishenjingwangluodejiegou)
- [栈和队列题解方法](https://www.oomspot.com/post/zhanheduilietijiefangfa)
- [数组LeetCode笔试](https://www.oomspot.com/post/shuzuleetcodebishi)
- [数据结构](https://www.oomspot.com/post/shujujiegou)
- [数据库事故](https://www.oomspot.com/post/shujukushigu)
- [操作系统初见？见了好多次，次次都要学！](https://www.oomspot.com/post/caozuoxitongchujianjianlehaoduocicicidouyaoxue)
- [怎么通俗的理解Netty呢？](https://www.oomspot.com/post/zenmetongsudelijienettyni)
- [富文本编辑器SpringBoot](https://www.oomspot.com/post/fuwenbenbianjiqispringboot)
- [字符串题解方法](https://www.oomspot.com/post/zifuchuantijiefangfa)
- [基础算法学习](https://www.oomspot.com/post/jichusuanfaxuexi)
- [双指针题解](https://www.oomspot.com/post/shuangzhizhentijie)
- [刷题加油](https://www.oomspot.com/post/shuatijiayou)
- [分布式锁初见](https://www.oomspot.com/post/fenbushisuochujian)
- [互联网基础架构图解](https://www.oomspot.com/post/hulianwangjichujiagoutujie)
- [二叉树题解方法](https://www.oomspot.com/post/erchashutijiefangfa)
- [三体语录](https://www.oomspot.com/post/santiyulu)
- [Swagger初见](https://www.oomspot.com/post/swaggerchujian)
- [Spring初见](https://www.oomspot.com/post/springchujian)
- [SpringSecurity图解](https://www.oomspot.com/post/springsecuritytujie)
- [SpringSecurityShiro初见](https://www.oomspot.com/post/springsecurityshirochujian)
- [SpringBoot异步定时邮件任务](https://www.oomspot.com/post/springbootyibudingshiyoujianrenwu)
- [SpringBootWeb初见](https://www.oomspot.com/post/springbootwebchujian)
- [SprinBootSpringData整合](https://www.oomspot.com/post/sprinbootspringdatazhenghe)
- [SpingBootDubboZookeeper分布式](https://www.oomspot.com/post/spingbootdubbozookeeperfenbushi)
- [Shiro登陆流程认证图解](https://www.oomspot.com/post/shirodengluliuchengrenzhengtujie)
- [Redis数据类型应用场景](https://www.oomspot.com/post/redisshujuleixingyingyongchangjing)
- [Redis conf分析](https://www.oomspot.com/post/redisconffenxi)
- [Radius协议学习](https://www.oomspot.com/post/radiusxieyixuexi)
- [RabbitMQ进阶](https://www.oomspot.com/post/rabbitmqjinjie)
- [RabbitMQ初见](https://www.oomspot.com/post/rabbitmqchujian)
- [Netty初见三大组件简单使用](https://www.oomspot.com/post/nettychujiansandazujianjiandanshiyong)
- [MySql分区、分表和分库](https://www.oomspot.com/post/mysqlfenqufenbiaohefenku)
- [MySQL实战45讲2125笔记](https://www.oomspot.com/post/mysqlshizhan45jiang2125biji)
- [MySQL实战45讲1620笔记](https://www.oomspot.com/post/mysqlshizhan45jiang1620biji)
- [MySQL实战45讲1015笔记](https://www.oomspot.com/post/mysqlshizhan45jiang1015biji)
- [Linux实战常用命令](https://www.oomspot.com/post/linuxshizhanchangyongmingling)
- [Java爬虫小项目](https://www.oomspot.com/post/javapachongxiaoxiangmu)
- [JavaNIO](https://www.oomspot.com/post/javanio)
- [JVM调优命令](https://www.oomspot.com/post/jvmdiaoyoumingling)
- [JVM深入](https://www.oomspot.com/post/jvmshenru)
- [JVM初见](https://www.oomspot.com/post/jvmchujian)
- [JVM优化](https://www.oomspot.com/post/jvmyouhua)
- [JAVA中直接用Jdbc就能操作数据库了，为什么还要用spring框架?](https://www.oomspot.com/post/javazhongzhijieyongjdbcjiunengcaozuoshujukuleweish)
- [Hash题解方法](https://www.oomspot.com/post/hashtijiefangfa)
- [HashMap的转化时机](https://www.oomspot.com/post/hashmapdezhuanhuashiji)
- [HashMap源码分析](https://www.oomspot.com/post/hashmapyuanmafenxi)
- [Github博客园初见](https://www.oomspot.com/post/githubchujian)
- [GC优化案例](https://www.oomspot.com/post/gcyouhuaanli)
- [ElasticSearch7 X X初见模仿京东搜索的实战](https://www.oomspot.com/post/elasticsearch7xxchujianmofangjingdongsousuodeshizh)
- [Docker初见](https://www.oomspot.com/post/dockerchujian)
- [CI/CD企业级DevOps](https://www.oomspot.com/post/cicdqiyejidevops)