本周分享环形链表定义单链表的某个节点的next不是null而是指向链表前面某个节点形成环遍历会无限循环。主要考察两点判断链表是否环如果有环如何找到这个环的入口一、判断是否有环快慢指针法分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点。因为fast是走两步slow是走一步其实相对于slow来说fast是一个节点一个节点的靠近slow的所以fast一定可以和slow重合。如果 fast 和 slow指针在途中相遇 说明这个链表有环。二、如何找到入口设头节点到入口处有x个节点入口到相遇处y个节点相遇处到入口z个节点快指针速度是慢指针速度的二倍2x y) x y n * (y z) #n为快指针绕的圈数推导得到x (n - 1) * (y z) z若令 n 1 得到 x z说明如果从头结点出发一个指针从相遇节点也出发一个指针这两个指针每次只走一个节点 那么这两个指针相遇的地方就是 环形入口的节点。即在相遇节点处定义一个指针index1在头结点处定一个指针index2。让index1和index2同时以每次一个节点速度移动 两指针相遇的地方为环形链表入口节点。e.g.力扣142环形链表II题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。代码示例structListNode*detectCycle(structListNode*head){structListNode*fasthead;structListNode*slowhead;while(fast!NULLfast-next!NULL){//判断是否有环fastfast-next-next;slowslow-next;if(fastslow){// 相交即有环开始找环形入口structListNode*ffast;structListNode*hhead;while(f!h){ff-next;hh-next;}returnh;//输出入口位置}}returnNULL;//链表中无环 输出NULL}链表相交定义 两个链表存在同一个节点对象内存地址相同该节点就是交点交点之后的所有节点都重合。只值相等不算相交相交链表一旦相交尾部一定相同核心思路利用双指针注意交点是指针相等创建两个指针curAcurB令A指向链表A的头结点B指向链表B的头结点求出两链表的长度并求出两链表长度差值让curA移动到和curB末尾对齐的位置比较curA和curB如果不相等同时向后移动当两者相等时找到交点e.g.力扣面试题02.07 链表相交题目描述给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回null。注意函数返回结果后链表必须保持其原始结构。代码示例structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structListNode*lNULL;structListNode*sNULL;intlenA0,lenB0,gap0;//求两个链表的长度lheadA;while(l!NULL){lenA;ll-next;}lheadB;while(l!NULL){lenB;ll-next;}//求长度差if(lenAlenB){lheadA;sheadB;gaplenA-lenB;}else{sheadA;lheadB;gaplenB-lenA;}//尾部对齐inti0;for(i0;igap;i){ll-next;}//移动检查相同元素while(l!NULL){if(ls){returnl;}ll-next;ss-next;}returnNULL;}双向链表链式储存结构的节点中只有一个指示直接后续的指针域由此从某个节点出发只能顺指针向后寻找其他节点。若要查找节点的直接前驱则必须从表头指针出发。为克服单链表这种单向性的缺点可利用双向链表。在双向链表中的节点有两个指针域一个指向直接后继另一个指向直接前驱。typedefintElemType;typedefstructnode{ElemType data;structnode*prev;//加入一个指向前驱的指针structnode*next;}Node;插入顺序先改新节点的 prev、next再修改相邻节点指针防止断链删除双向链表优势不用找前驱p-prev直接拿到前一个节点