在线客服

互换单链表里的连接点 medium题型连接

adminadmin 报建百科 2024-04-24 37 0
互换单链表里的连接点 medium题型连接

- leetcode 24 两组互换单链表里的连接点 medium

题型连接:https://leetcode.com/problems/swap-nodes-in-pairs/

构思: 单链表题绘图很重要,依据绘图尝试在2个连接点及其前节点偏向更改逻辑性,提前储存后连接点便捷循环系统下一次实行。

编码:

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummynode = new ListNode(-1, head);
        ListNode cur = head;
        ListNode pre = dummynode;
        while (cur != null && cur.next != null) {
            ListNode post = cur.next;
            pre.next = cur.next;
            cur.next = cur.next.next;
            post.next = cur;
            pre = cur;
            cur = post;
            cur = cur.next.next;
        }
        return dummynode.next;
    }
}

递交出错 (2):

第1次: Found cycle, 主要原因是没绘图因此思路不清,单链表偏向更改的思路不清楚造成环, 此外并没有考虑清楚循环系统实际操作的范畴。

第2次: 第2对逐渐不旋转,主要原因是缺少了将表针移到下一轮周而复始的实际操作。

- leetcode 19 删掉单链表的倒数第N个连接点 medium

题型连接:https://leetcode.com/problems/remove-nth-node-from-end-of-list/

构思: 快慢指针,快慢指针的间距应该给n。确保慢表针最后局限在要删节点的前一个,便捷删掉实际操作。另也要合适地探索单链表结尾。

编码:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummynode = new ListNode(-1, head);
        ListNode fast = dummynode;
        ListNode slow = dummynode;
        for (int i = 0; i < n; i  ) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummynode.next;
    }
}

递交出错 (2):

第1次: 循环系统int i 不提供初值,

第2次: 快慢指针从head逐渐造成不正确,立即独立考虑到了只有一个节点状况而加上快慢指针同歩往前标准,当前节点也需要为null。应用dummynode要了解不一样层面,一是区别对待只求便捷储存单链表头并回到,二是可以加整个单链表之中参与到循环系统实际操作的思路中。

- leetcode 142 环形链表II medium

题型连接:https://leetcode.com/problems/linked-list-cycle-ii/

构思: 快慢指针,单链表题必须绘图,应用给出基本case发觉规律性。题型的目的是寻找环起始点,则假定单链表起始点到环起始点距离为x。设置快表针每一次走2步,慢表针每一次走1步,则快表针在通过n圈挪动后环外必定交叉点,设环起始点到交叉点为y,交叉点 到环起始点为z。亦有式子$2(x y) = n(y z)$,依据式子可推测出$x=(n-1)y nz$, $y=(n-1)y nz$, 则$x=z$。当发现交叉点后,把交叉点和起止点与此同时挪动,在相同的时候会寻找环起始点。

编码:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode start = head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                while (start != fast) {
                    start = start.next;
                    fast = fast.next;                    
                }
                return start;
            }
        }
        return null;
    }
}

递交出错 (2):

第1次: 不正确较为(slow.val == fast.val), 要相对比较并不是值,反而是连接点是不是相同,即(slow == fast)

第2次: 没有考虑仅有2个点成环突发情况,必须根据实际test case出错改善。

- leetcode 160?单链表交叉 easy

题型连接:https://leetcode.com/problems/linked-list-cycle-ii/

构思: 用两个表针主要从2个单链表的页眉逐渐挪动,探寻连接点相同位置,假如相同则回到随意表针,假如不相同则往前挪动,如果遇见单链表尾端则使表针总其它的另外一个单链表的页眉逐渐挪动,如此往复则一定会处理链表长度不均衡问题。

编码:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode listA = headA;
       ListNode listB = headB;
       if (headA == null || headB == null) {
           return null;
       }
       while (listA != listB) {
           listA = listA == null ? headB : listA.next;
           listB = listB == null ? headA : listB.next;
       }
       return listA;
    }
}

递交出错 (1):

第1次: 边界值难题,没有考虑两单链表都为空的现象。

疑惑点,求解答!!! ??如果两单链表都不为空也不交叉仿佛没有考虑,不知道该怎么了解?

本站是一个以CSS、JavaScript、Vue、HTML为中心的前端开发技术网址。我们的使命是为众多前端工程师者提供全方位、全方位、好用的前端工程师专业知识和技术服务。 在网站上,大家可以学到最新前端开发技术,掌握前端工程师最新发布的趋势和良好实践。大家提供大量实例教程和实例,让大家可以快速上手前端工程师的关键技术和程序。 本站还提供了一系列好用的工具软件,帮助你更高效地开展前端工程师工作中。公司提供的一种手段和软件都要经过精心策划和改进,能够帮助你节约时间精力,提高研发效率。 此外,本站还拥有一个有活力的小区,你可以在社区里与其它前端工程师者沟通交流技术性、交流经验、处理问题。我们坚信,街道的能量能够帮助你能够更好地进步与成长。 在网站上,大家可以寻找你需要的一切前端工程师网络资源,使您成为一名更加出色的网页开发者。欢迎你添加我们的大家庭,一起探索前端工程师的无限潜能!
代办报建

本公司承接江浙沪报建代办施工许可证。
联系人:张经理,18321657689(微信同号)。

喜欢0发布评论

评论列表

发表评论

  • 昵称(必填)
  • 邮箱
  • 网址