首页 > 编程语言 >代码随想录算法训练营,8月31日 | 24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交,142.环形链表II

代码随想录算法训练营,8月31日 | 24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交,142.环形链表II

时间:2024-08-31 18:27:04浏览次数:11  
标签:ListNode 随想录 fast next 链表 curB curA 节点

24. 两两交换链表中的节点
题目链接:24. 两两交换链表中的节点
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰两两交换链表中的节点
日期:2024-08-31

做前思路:用上虚拟头指针,从头开始,先指向2再到1,再到3,但要注意保留原本的结点。
Java代码如下:

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode node1;
        ListNode node2;
        ListNode node3;
        ListNode cur = dummyHead;
        while(cur.next != null && cur.next.next != null){
            node1 = cur.next;
            node2 = cur.next.next;
            node3 = cur.next.next.next;
            cur.next = node2;
            cur.next.next = node1;
            cur.next.next.next = node3;
            cur = cur.next.next;
        }
        return dummyHead.next;
    }
}

总结:做此题得有图,我为了方便就将当前结点后的3个结点全部保存了一遍,当然也可以省略一些。

19.删除链表的倒数第N个节点
题目链接:19.删除链表的倒数第N个节点
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰删除链表的倒数第N个节点
日期:2024-08-31

做前思路:第一反应要是删除的是第n个结点,而不是倒数第n个就好了,遍历一遍链表得到它长度,将其还算为删除第m个结点;当然在,学习后会想到快慢双指针来,实际上我认为这是一个数学小技巧,快指针先走n步后,快慢指针一起走,快指针走到尾,此时慢指针就在要删的结点那个位置了,当然,为了后面删除操作更方便,我们需要将慢指针移前一位,所以快指针走n+1不就行了。
Java代码如下:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        while(n-- > 0){
            fast = fast.next;
        }
        fast = fast.next;//快指针走n+1
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyHead.next;
    }
}

总结:这也算是一道双指针来优化算法的案例,双指针作用主要体现在了简单的数学加减上,能够定位到倒数n个结点的位置才是关键。

面试题 02.07. 链表相交
题目链接:面试题 02.07. 链表相交
文档讲解︰代码随想录(programmercarl.com)
日期:2024-08-31

做前思路:想象两个相同长度的链表,要找它们相交点,只需要依次一个一个对比每一个指针是不是有相同就行,指针一旦相同,后面的内容也一定会相同(链表的基本属性了),而如果两个长度不一样的呢,如果还从头依次开始比,那么永远找不到相同的指针,因为最基本的它们链表长度都不一样了,怎么还能相交呢(这里链表只能1对1,1对多那是树了),所以我们只有想办法先将两根链表尾部对齐后,才能再按照两个相同长度的链表一样的操作,找到相交位置。
Java代码如下:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != null){
            curA = curA.next;
            lenA++;
        }
        while(curB != null){
            curB = curB.next;
            lenB++;
        }
        curA = headA;
        curB = headB;
        if(lenB > lenA){
            curA = headB;
            curB = headA;
            int temp = lenA;
            lenA = lenB;
            lenB = temp;
        }
        int gap = lenA - lenB;
        while(gap-- > 0){
            curA = curA.next;
        }
        while(curA != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

总结:做题时出了个错,想了挺久代码是这样的:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != null){
            curA = curA.next;
            lenA++;
        }
        while(curB != null){
            curB = curB.next;
            lenB++;
        }
        //curA = headA; 这两个没有
        //curB = headB;
        if(lenB > lenA){
            curA = headB;
            curB = headA;
            int temp = lenA;
            lenA = lenB;
            lenB = temp;
        }
        int gap = lenA - lenB;
        while(gap-- > 0){
            curA = curA.next;
        }
        while(curA != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

当时想着我不是已经curA = headB; curB = headA;了吗,却没有考虑到当lanA > lanB情况下cuaA, cuaB仍是null,通过debug才搞明白。

**142.环形链表II **
题目链接:142.环形链表II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰环形链表II
日期:2024-08-31

做前思路:一道颇有难度,用上快慢指针和数学思维的题,首先,考虑快慢指针是来干什么,找是不是有环,如果快的走两步能追上慢的走一步的,那一定是有环的,然后是怎么找入口,这点建议直接看文档,这里权当是记住了该怎么找,作为结论:两个指针一个是在头,一个是在相遇点,一起前进一步,相遇点便是入口。
Java代码如下:

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(fast == slow){
                ListNode index1 = fast;
                ListNode index2 = head;
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

总结:代码简洁的后果就是逻辑的要求增多,确定有没有环比较好理解,找入口只能先记住了,推导再议。

标签:ListNode,随想录,fast,next,链表,curB,curA,节点
From: https://www.cnblogs.com/wowoioo/p/18390559

相关文章

  • 信息学奥赛初赛天天练-80-NOIP2015普及组-基础题5-错位排列、二叉树、完全二叉树、叶
    NOIP2015普及组基础题521重新排列1234使得每一个数字都不在原来的位置上,一共有()种排法22一棵结点数为2015的二叉树最多有()个叶子结点2相关知识点1)错位排列考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就......
  • leetcode刷题day4|链表部分(24. 两两交换链表中的节点 、19.删除链表的倒数第N个节点、
    前言:链表练习的第二天,对链表的理解加深了24.两两交换链表中的节点这个题一开始的思路是用cur和next两个指针来做,但是绕来绕去绕迷糊了,最后超时了。把错误的代码放在下面警醒大家:主要问题出现在这两行代码,next.next发生了更改。next.next=next.next.next;next.next.nex......
  • leetcode刷题day3|链表部分( 203.移除链表元素、707.设计链表、206.反转链表)
    前言:链表部分之前刷过一些题,掌握的还可以,希望可以顺利把这部分题刷完。203.移除链表元素思路:自己创建一个头节点,使新的头节点指向旧的头节点。错误尝试:一开始考虑的比较复杂,设置了指针pre,能够想到直接比较cur.next.val和val的值会使代码更加简洁,但也要注意想清楚如果删除......
  • 数据结构-单链表-详解-2
    数据结构-单链表-详解-21.前言2.创建新结点3.头插与尾插3.1头插3.2尾插空链表找尾4.头删与尾删4.1头删4.2尾删1.前言在数据结构-单链表-详解-1中,我们不仅了解了单链表的基本概念,还掌握了如何创建和打印单链表。今天,我将详细讲解如何对单链表进行头尾部的插入、......
  • 单链表应用
    基于单链表实现通讯录项目//Contact.c#define_CRT_SECURE_NO_WARNINGS1#include"contact.h"#include"list.h"//初始化通讯录voidInitContact(contact**con){ con=NULL; }//添加通讯录数据voidAddContact(contact**con){ PeoInfoinfo; printf("addres......
  • 单链表
    目录1.链表的概念及结构2.单链表的实现3.链表的分类                        1.链表的概念及结构概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 链......
  • 代码随想录day46 || 647 回文子串, 516 最长回文子序列
    647回文字串funccountSubstrings(sstring)int{ //动规五部曲 //dp[i][j]表示s[i:j+1]区间是否是一个回文 //ifs[i]==s[j]{ifi-j<=1||dp[i+1][j-1]==true{dp[i][j]==true}} //初始化为false //从下往上,从左往右 //print varcountint var......
  • 代码随想录算法day4 - 链表2
    题目124.两两交换链表中的节点给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]示例2:输入:head=[]输出:[]示例3:输入:head=[1]输出:[1]......
  • list容器---深入探索STL中的双向链表
    目录一、引言二、list容器原理三、list容器的常用操作  1.创建list容器  2.添加元素  3.删除元素  4.访问元素  5.遍历list容器四、list容器的优缺点五、实际应用场景六、总结        本文将详细介绍C++STL中的list容器,包括其原理、常用......
  • 代码随想录算法训练营,8月30日 | 203.移除链表元素, 707.设计链表, 206.反转链表
    链表理论基础1.单链表:数据域和指针域(指向下一个结点的位置)组成,头结点,结尾为空指针;双链表:多了一个指向前一个结点的指针;循环链表:结尾指向头结点。2.链表在内存中的存储不是顺序的,跟数组不同,要找一个数据只能通过前一个数据来找,所有这就导致链表的查询比数组麻烦,但是插入删除数据......