首页 > 其他分享 >知识改变命运 数据结构【链表面试题】

知识改变命运 数据结构【链表面试题】

时间:2024-08-17 23:52:48浏览次数:16  
标签:head null ListNode 试题 fast next 改变命运 数据结构 cur

1. 删除链表中等于给定值 val 的所有节点。 OJ链接

在这里插入图片描述

 public ListNode removeElements(ListNode head, int val) {
        if (head==null) {
            return null;
        }
        ListNode cur=head.next;
        ListNode pre=head;
        while(cur!=null) {
            if(cur.val==val) {
                pre.next=cur.next;
                cur=cur.next;
            }
            else {
                pre=cur;
                cur=cur.next;
            }
           
        }
         if(head.val==val)
            head=head.next;
    return head;
    }
}

在这里插入图片描述

2. 反转一个单链表。 OJ链接

在这里插入图片描述

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
                return null;
            }
            
            ListNode cur = head.next;
            head.next = null;
            while (cur != null) {
                ListNode C = cur.next;
                cur.next = head;
                head = cur;
                cur = pre;
               
            }
            return head;

        }
        
        
    }

3. 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结

点。OJ链接
在这里插入图片描述

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

    }
}

4. 输入一个链表,输出该链表中倒数第k个结点。 OJ链接

在这里插入图片描述

方法1

 public int kthToLast2( int k) {
        if(k <= 0 ) {
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;

        int count = 0;
        while (count != k-1) {
            fast = fast.next;
            if(fast == null) {
                return -1;
            }
            count++;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

方法2

class Solution {
    public int kthToLast(ListNode head, int k) {
          ListNode cur=head;
        while(k!=0) {
            if (cur==null) {
                return -1;
            }
            cur=cur.next;
            k--;
        }
        if (k==0) {
            while(cur!=null) {
                cur=cur.next;
                head=head.next;
            }
            return head.val;
        }
        return -1;
    }
}

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ

在这里插入图片描述

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       if(list1==null) {
                return list2;
            }
            if (list2==null) {
                return list1;
            }
            ListNode temp;
            if(list1.val>list2.val) {
                temp=list2;
                list2=list2.next;

            }
            else {
                temp=list1;
                list1=list1.next;
            }
            ListNode head=temp;
            while(list1!=null&&list2!=null) {
                if(list1.val>list2.val) {
                    temp.next=list2;
                    list2=list2.next;
                    temp=temp.next;
                }
                else {
                    temp.next=list1;
                    list1=list1.next;
                    temp=temp.next;
                }

            }
            if(list1!=null) {
                temp.next=list1;
            }
            if(list2!=null) {
                temp.next=list2;
            }
            return head;
    } 
    
}

6. 编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。OJ链接

在这里插入图片描述

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode cur = pHead;
        ListNode be = null;
        ListNode bs = null;
        ListNode as = null;
        ListNode ae = null;
        while (cur != null) {
            if (cur.val < x) {
                if (bs == null) {
                    bs = be = cur;
                } else {
                    be.next = cur;
                    be=be.next;
                }
            } else {
                if (as == null) {
                    as = ae = cur;
                } else {
                    ae.next = cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if(be==null) {
            return as;
        }
        if(ae!=null) {
            ae.next=null;
        }
        be.next = as;
        return bs;
        

    }
}

7. 链表的回文结构。OJ链接

在这里插入图片描述

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
          ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode cur=slow.next;
        ListNode curN=cur;
        while(curN!=null) {
            curN=curN.next;
            cur.next=slow;
            slow=cur;
            cur=curN;
        }
        while(slow!=head) {
            if(head.val!=slow.val) {
                return false;
            }
            if (head.next==slow) {
                return true;
            }
                head=head.next;
                slow=slow.next;
        }
        return true;
    }
}

8. 输入两个链表,找出它们的第一个公共结点。OJ链接

在这里插入图片描述

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl=headA;
        ListNode ps=headB;
        int len1=size(pl);
        int len2=size(ps);
        int leng=Math.abs(len1-len2);
        if(len1>len2) {
            while(leng!=0) {
                pl=pl.next;
                leng--;
            }
        }else {
            while (leng !=0) {
                ps=ps.next;
                leng--;
            }
        }
        while(ps!=null&&pl!=null) {
              if(ps==pl) {
                  return ps;
              }
              ps=ps.next;
              pl=pl.next;
        }
        return null;
    }
    public int size(ListNode head) {
        int count=0;
        while (head!=null) {
            head=head.next;
            count++;
        }
        return count;
    }
}

9. 给定一个链表,判断链表中是否有环。 OJ链接

在这里插入图片描述

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null) {
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow) {
                return true;
            }  
        } return false;
    }
} 

【思路】
快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表
带环则一定会在环中相遇,否则快指针率先走到链表的末尾。比如:陪女朋友到操作跑步减肥。
【扩展问题】
为什么快指针每次走两步,慢指针走一步可以?
假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快
指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离
就缩小一步,不会出现每次刚好是套圈的情况,因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指
针的,即相遇。
快指针一次走3步,走4步,…n步行吗?
在这里插入图片描述
按上面的方法,每次快指针走三步,慢指针走一步,永远不会相遇,因为快指针把慢指针套圈了。
因此只有快指针走2步,慢指针走一步,即使慢指针被套圈,slow和fast也是同一位置。

10. 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL OJ链接

在这里插入图片描述

public class Solution {
    public ListNode detectCycle(ListNode head) {

        if(head==null) {
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast) {
                break;
            }
        }
        if(fast==null||fast.next==null) {
            return null;
        }
        fast=head;
        while (fast!=slow) {
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}

在这里插入图片描述

标签:head,null,ListNode,试题,fast,next,改变命运,数据结构,cur
From: https://blog.csdn.net/2402_84062064/article/details/141233497

相关文章

  • 数据结构--顺序表
    目录一、引言二、顺序表的基本概念与结构1.概念2.基本结构三、顺序表的分类四、动态顺序表的实现 1.结构定义2.相关功能实现1.初始化2.销毁3.扩容4.打印 5.头插6.尾插 7.头删 8.尾删 9.指定插入 10.指定删除 11.查找  五、完整代码1.SeqList.h2......
  • 这是我见过的(最全面,最优质的)Java的List集合常见面试题汇总,一文讲完,通俗易懂,看完不吊打
    Arraylist和数组(Array)的区别?ArrayList内部基于动态数组实现,比Array(静态数组)使用起来更加灵活:ArrayList会根据实际存储的元素动态地扩容或缩容,而Array被创建之后就不能改变它的长度了。ArrayList允许你使用泛型来确保类型安全,Array则不可以。ArrayList中只能存储对象......
  • 【模板】数据结构
    数据结构权值BIT上二分struct{intn,t[N]; intkth(intk){ intp=0;rFor(i,__lg(n),0)if(p+(1<<i)<n&&k>t[p+(1<<i)])p+=1<<i,k-=t[p]; returnp+1; }};zkw线段树李超线段树线段树合并,分裂可持久化\(01......
  • 数据结构----链表
    一丶概念     链表又称单链表、链式存储结构,用于存储逻辑关系为“一对一”的数据。      和顺序表不同同,使用链表存储数据,不强制要求数据在内存中集中存储,各个元素可以分散存储在内存中。二丶特点     特点:内存不连续,通过指针进行连接 ......
  • 【面试宝典】java基础面试题总结[上]
    一、Java中有几种基本数据类型?各占多少字节?在Java中基本数据类型有8个,占用的字节分别是整型byte(1个字节)、short(2个字节)、int(4个字节)、long(8个字节);浮点型float(4个字节)、double(8个字节);布尔类型boolean;字符类型char(2个字节)。二、String类能被继承吗?为什么?Stri......
  • 高级java每日一道面试题-2024年8月16日-设计模式篇-解释装饰者模式和代理模式的区别?
    如果有遗漏,评论区告诉我进行补充面试官:解释装饰者模式和代理模式的区别?我回答:在Java中,装饰者模式(DecoratorPattern)和代理模式(ProxyPattern)都是常用的设计模式,它们在结构上看起来有些相似,但实际上它们的目的、应用场景和实现方式存在明显的区别。下面详细解释这两种......
  • Java面试题--JVM大厂篇之掌控Java未来:深入剖析ZGC的低停顿垃圾回收机制
    Java面试题--JVM大厂篇之掌控Java未来:深入剖析ZGC的低停顿垃圾回收机制引言:正文:一、ZGC的核心机制1.并发标记和重定位(Relocation)2.染色指针(ColoredPointers)与读屏障(LoadBarriers)二、实际案例分析1.在线游戏服务器2.金融交易系统三、解决方案和技巧1.调整ZGC参数......
  • 数据结构与算法——BFS(广度优先搜索)
    算法介绍:广度优先搜索(Breadth-FirstSearch,简称BFS)是一种遍历或搜索树和图的算法,也称为宽度优先搜索,BFS算法从图的某个节点开始,依次对其所有相邻节点进行探索和遍历,然后再对这些相邻节点的相邻节点进行探索,直到遍历完所有的节点。BFS算法使用队列来辅助实现,将起始节点放入队列......
  • 一篇总结Redis面试题知识点
    为什么要使用Redis        使用Redis主要是因为Redis的三大特性,高可靠高并发高性能。在请求访问数据时,如果直接从数据库中获取数据,它的并发量可能只有1000次/秒,这已经算是很不错的表现。如果在程序启动的时候就将数据放到Redis中,数据访问时如果直接从缓存中读取,他的性......
  • 数据结构中的双向链表
    1.链表的分类链表的结构非常多样,以下情况组合起来就是8种(2x2x2)链表结构:  在带头链表中,除了头结点,其他结点均存储有效的数据。头结点是占位子的,也叫做“哨兵位”。head结点就是头结点。 循环的链表尾结点不为NULL,不循环的链表尾结点为NULL单链表:不带头单向不循环链......