小工具知识网

当前位置: 首页 > 行业知识 > 代码随想录刷题day04|两两交换&删除倒N&链表相交&环形链表

行业知识

代码随想录刷题day04|两两交换&删除倒N&链表相交&环形链表

2026-11-16 14:08:48 来源:互联网转载

文章目录

  • day04学习内容
  • 一、 两两交换链表中的节点
    • 1.错误写法1
    • 2.正确写法1
    • 2.正确写法2
    • 二、删除倒数第N个节点(双指针法)
      • 1.正确写法1
      • 三、链表相交
        • 1.正确写法-双指针
        • 四、环形链表
          • 1.思考
          • 2.正确写法
          • 总结
            • 1.感想
            • 2.���维导图

              day04学习内容

              day04主要内容

              • 两两交换链表中的节点
              • 删除倒数第N个节点
              • 链表相交
              • 环形链表

                一、 两两交换链表中的节点

                24原题链接

                1.错误写法1

                class Solution {    public ListNode swapPairs(ListNode head) {        if(head==null){            return null;        }        ListNode dummy = new ListNode(-1,head);        ListNode cur = dummy;        while(cur.next!=null&&cur.next.next!=null){            ListNode tempNode1 = cur.next;            ListNode tempNode2 = cur.next.next;            ListNode tempNode3 = cur.next.next.next;            cur.next = tempNode2;            tempNode2.next = tempNode1;            tempNode1.next = tempNode3;              cur = tempNode2; //注意就是这一句话写错了,为什么错了,看下面分析        }        return dummy.next;    }}

                假如head = 1->2->3->4->null,代码执行到tempNode1.next = tempNode3这一步时,此时链表的变化过程如下俩图(数字就是交换的执行顺序),

                因为要让cur重新指向需要交换的2个节点的前1个节点,此时节点【3】的前一个节点是【1】,所以此时cur=N1而不是cur=N2

                2.正确写法1

                class Solution {    public ListNode swapPairs(ListNode head) {        if(head==null){            return null;        }        ListNode dummy = new ListNode(-1,head);        ListNode cur = dummy;        while(cur.next!=null&&cur.next.next!=null){            ListNode tempNode1 = cur.next;            ListNode tempNode2 = cur.next.next;            ListNode tempNode3 = cur.next.next.next;            cur.next = tempNode2;            tempNode2.next = tempNode1;            tempNode1.next = tempNode3;              cur = tempNode1;        }        return dummy.next;    }}

                2.正确写法2

                `采用双指针

                class Solution {    public ListNode swapPairs(ListNode head) {        if(head==null){            return null;        }        ListNode dummy = new ListNode(-1,head);        ListNode cur = dummy;        while(cur.next!=null&&cur.next.next!=null){            ListNode tempNode1 = cur.next;            ListNode tempNode3 = cur.next.next.next;            cur.next = cur.next.next;            cur.next.next = tempNode1;//注意这里不要写成cur.next.next.next了,画图理解一下就知道为什么要这么写了            tempNode1.next = tempNode3;              cur = tempNode1;        }        return dummy.next;    }}

                二、删除倒数第N个节点(双指针法)

                19原题链接

                思路:

                这一题主要是想明白,怎么找到倒数第N个节点。

                1. 问题1:

                  我就没想到快指针要先走N+1步,看了题解和视频才看明白的,才知道这个思路

                2. 问题2

                  先让快指针走n步,不知道怎么写代码。。。离天下之大谱

                3. 问题3

                  不知道怎么让fast和slow同时移动,直到fast==null终止

                好家伙,很简单的一题就有三个问题了,基本等于一句都不会写。

                1.正确写法1

                class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        ListNode dummy = new ListNode(-1,head);        ListNode fast = dummy;        ListNode slow = dummy;        for(int i=0;i            fast = fast.next;        }        while(fast!=null){            fast = fast.next;            slow = slow.next;        }        slow.next= slow.next.next;        return dummy.next;    }}    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 (fast == slow) {// 相遇                ListNode index1 = fast;                ListNode index2 = head;                while (index1 != index2) {                    index1 = index1.next;//不要写成index1=fast.next了                    index2 = index2.next;                }                return index1;            }        }        return null;    }}

上一篇:原神怎么替换服务器?

下一篇:关闭休眠命令,操作详解与影响解析