Day04 链表02

发布时间:2024年01月18日

由于链表知识的缺失,所以去补充了一些链表的基础知识。

链表(ListNode)基础知识

视频地址:第3周01--2.5线性表的链式表示和实现1--链表概念_哔哩哔哩_bilibili

链表特点

物理位置不一定连续,逻辑次序和物理次序不一定相同。

组成元素

结点:包括两个域。

? ? ? ? (1)数据域(data):存着数据。

? ? ? ? ? ? ? ? 类型取决于数据类型

? ? ? ? (2)指针域(next):存着下一个数据的地址。

链表:若干个指针连接在一起。

头指针,头结点和首元结点

头指针:只有地址。

头结点:记录第一个元素的位置。(就是代码随想录里的虚拟头节点,不是数据域的元素,不算进表长)

? ? ? ? 单链表由头指针确定因此可以由头指针命名。

小知识:null=^=0

首元结点:第一个有元素的节点。

设置头指针的好处:

? ? ? ? (1)首元结点的处理可以和其他节点一样

? ? ? ? (2)便于空表和非空表的处理

24. 两两交换链表中的节点

文章链接:代码随想录

题目

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

24.两两交换链表中的节点-题意

细节:长度有奇有偶

我的思路

利用虚拟头节点,指针指向要操作的元素的前一个元素,然后利用两个容器写转变位置。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0,head);
        ListNode cur=dummy;
        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;
        cur.next.next.next=temp2;
        cur=cur.next.next;//记得移动指针
        }
        return dummy.next;
    }
}

19.删除链表的倒数第N个节点

文章链接:代码随想录

题目

给你一个链表,删除链表的倒数第?n?个结点,并且返回链表的头结点

我的思路

用while循环遍历链表找出链表的长度,再用长度操作。

双指针思路

一个快指针,一个慢指针,快指针先走n次,慢指针快指针一起走就能找到要删除的数。但是要用的是删除元素前面的数,所以要再+1。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy=new ListNode(0,head);
        ListNode f=dummy;
        ListNode s=dummy;
        while(n>0&&f.next!=null){
            f=f.next;
            n--;
        }
        while(f.next!=null){
            f=f.next;
            s=s.next;
        }
        if(s.next!=null&&s.next.next!=null){   s.next=s.next.next;
}else{
    s.next=null;
}
     
        return dummy.next;
    }
}

环形链表

文章链接:代码随想录

题目

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

循环链表

?双指针思路

1.判断是否有环:让快指针走2格慢指针走一格如果有环则会相遇

2.找到环的位置:设没有环的地方长度为x,相遇前转的圈是y相遇后的环为z。计算根据slow移动的距离*2=fast的距离列方程得出x=(n-1)(y+z)+z。说明x距离=y的距离。定义两个指针。一个从相遇的点出发,另一个从头出发。相遇的点就是环的人口。没有则返回null。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
      
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){//如果没有环的话会出现null
        
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                ListNode index1=slow;
                ListNode index2=head;
                while (index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                 return index1; 
             }
          

        }
         return null;
    }
}

面试题0207链表相交

文章链接:代码随想录

题目

给你两个单链表的头节点?headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

思路

首先将两个链表对向右对其,然后挨个找地址相同不相同。

对其过程:求出链表A长度,求出B长度,相减得到长度c将指针B移到c位置上。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA=headA,curB=headB;
        int lenA=0,lenB=0;
        while(curA!=null){
            lenA++;
            curA=curA.next;

        }
        while(curB!=null){
            lenB++;
            curB=curB.next;

        }
        curA=headA;
        curB=headB;
        if(lenA>lenB){
            for(int i=0;i<lenA-lenB;i++){
                curA=curA.next;
            }
        }
        if(lenB>lenA){
            for(int i=0;i<lenB-lenA;i++){
                curB=curB.next;
            }
        }
        while(curA!=null){
            if(curA==curB){
                return curA;
            }else{
                curA=curA.next;
                curB=curB.next;
            }
        }
        return null;
    }
}
改进

中间比较大小求长度可以改成如果A小于B就让指针A和指针B,长度A长度B交换位置。

总结

学习了三个小时,补充了链表基础,对链表的理解更加深刻了。

文章来源:https://blog.csdn.net/nagireo/article/details/135648818
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。