行业知识
Day4 LeeCode:24. 两两交换链表中的节点 面试题 02.07. 链表相交 19.删除链表的倒数第N个节点 142. 环形链表 II
24. 两两交���链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]输出:[2,1,4,3]
思考:本题如果把图画清楚后,就是一道简单的模拟题
本题加上一个虚拟头节点,就不用考虑交换的数在链表头部的特殊情况了,会方便很多
图解:
循环结束条件:
当cur.next==null 或者cur.next.next==null时,后面不用在继续交换了,故 while(cur.next != null && cur.next.next != null),这里包括了原链表本身为空和只有一个结点的情况
出现超出时间限制:
temp1,temp2写在while循环外面,一直没更新temp1和temp2;
代码参考:
class Solution { public ListNode swapPairs(ListNode head) { ListNode dummyHead=new ListNode(-1,head); ListNode cur=dummyHead; while(cur.next != null && cur.next.next != null){ ListNode temp1=cur.next; ListNode temp2=cur.next.next.next; cur.next=cur.next.next; cur.next.next=temp1; temp1.next=temp2; cur=cur.next.next; } return dummyHead.next; }} 19.删除链表的倒数第N个节点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2输出:[1,2,3,5]
思考:如何只遍历一遍就实现删除?
我们可以使用两个指针,两指针之间相差N+1个位置,当fast指针移动到尾端,也就是为fast==null时,slow指针刚好指向倒数第N个结点的前一结点
简化代码:
使用虚拟头节点,可以不用单独考虑要删除的结点为首结点的情况
图解:
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummyHead = new ListNode(-1,head); ListNode fast=dummyHead; ListNode slow=dummyHead; while(n-->=0&&fast!=null){ fast=fast.next; } while(fast!=null){ slow=slow.next; fast=fast.next; } slow.next=slow.next.next; return dummyHead.next; }} 面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
图示两个链表在节点 c1 开始相交:
注意:
本题中的相交是指针相同,不是数字相同
本题中相交的结点以及之后的结点会一直相交,
所以相交结点的个数一定小于等于链表A,B之中的的最小链表长度
思考:我们先求出两条链表的长度差,让长的链表的尾端和短链表尾端对其齐,从此时开始依次比较两链表的结点是否相同
代码参考:
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA=headA; ListNode curB=headB; int la=0,lb=0; //求A的长度 while(curA!=null){ curA=curA.next; la++; } while(curB!=null){ curB=curB.next; lb++; } int def=Math.abs(la-lb); if(la0){ curA=curA.next; } while(curA!=null){ if(curA==curB){ return curA; } curA=curA.next; curB=curB.next; } return null; }} 142. 环形链表 II
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1输出:返回索引为 1 的链表节点解释:链表中有一个环,其尾部连接到第二个节点。
如何判断链表有环,我们定义两个移动速度不同的指针slow和fast,如果链表存在环,那么两个指针一定会相遇,反之则不存在环
如何判断环的入口:
假设快指针一次走两个结点,慢指针一次走一个结点,相遇时一定有 (x + y) * 2 = x + y + n (y + z),联想追击问题,n表示快指针在环中绕了几圈
化简得:x = (n -1)(y + z) +z
特殊的,当n=1时,表示x=z 表示当快指针在环中绕一圈和慢指针相遇时x=z
此时如果用两个速度一样的指针,一个从头结点开始走,一个从上一次的相交结点开始走,它们各自走x(x=z)个结点后会在环入口相遇
当n=2时,表示x=y+z+z
此时如果用两个速度一样的指针,一个从头结点开始走,一个从上一次的相交结点开始走,A指针走x个结点,B指针走y+z+z个结点后会在环入口相遇
依次类推
我们可以知道,当两个速度一样的指针,一个从头结点开始走,一个从上一次的相交结点开始走,A指针走x个结点,它们最终会在入口处相遇
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; //快慢指针相遇,则有环,我们找入口 if(slow==fast){ ListNode temp1=head; ListNode temp2=slow; while(temp1!=temp2){ temp1=temp1.next; temp2=temp2.next; } return temp1; } } return null; }}