小工具知识网

当前位置: 首页 > 行业知识 > Day4 LeeCode:24. 两两交换链表中的节点 面试题 02.07. 链表相交 19.删除链表的倒数第N个节点 142. 环形链表 II

行业知识

Day4 LeeCode:24. 两两交换链表中的节点 面试题 02.07. 链表相交 19.删除链表的倒数第N个节点 142. 环形链表 II

2026-11-19 09:41:57 来源:互联网转载

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;    }}

上一篇:Cadvisor源码编译全攻略,轻松上手,步步为赢!

下一篇:Tim在线实时交流,即刻开启无缝沟通之门!