【代码题】五道链表面试题

简介: 【代码题】五道链表面试题

1.移除链表元素


给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回新的头节点 。

 

7900e5fc64684eaf913f5c68820eb84d.png


  题解 :


思路:

1.既然需要删除val,那么我们要做的一定有找到val值这个操作。

2.因为是单链表,无法返回到上一个节点,因此我们需要使用双指针。

3.进入while,寻找val,如果找到就将val删除(prev.next=cur.next),删除后,只让cur向后走,因为我们找到的下一个值也可能是val值。如果没有找到,就让prev和cur都向后走一步。

4.上方判断跳过了头节点,拿出来单独判断。

5.最终返回head。


代码:

   public ListNode removeElements(ListNode head, int val) {
        //判断链表是否为空
        if(head==null) {
            return null;
        }
        //双指针思想
        ListNode cur=head.next;
        ListNode prev=head;
        while(cur!=null) {
            //删除
            if(cur.val==val) {
                prev.next=cur.next;
                cur=cur.next;  
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        //判断第一个是否为key
        if(head.val==val) {
            head=head.next;
        }
        return head;
    }


2.反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

       题解 :


思路:

1.先判断特殊情况,无节点和一个节点的情况。

2.用cur向后走,用curNext记录cur下一个节点。

3.运用头插法将cur一个一个插入到heda前面


15179ba5c4e94b989dad9ff565f7375d.png


代码:

public ListNode reverseList(ListNode head) {
        //无节点情况
        if(head==null){
            return null;
        }
        //一个节点情况
        if(head.next==null) {
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        //头插法
        while(cur!=null) {
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }


3.链表的中间结点

给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

       题解 :


思路:

1.此题运用了,在相同时间和相同路程中,V2是V1的二倍,那么,V2走到最后,V1就刚好走2到中间。

2.运用双指针、快慢指针思想。

3.让prev走两步,让cur走一步,当prev走到尾节点时,cur刚好在中间节点。



public ListNode middleNode(ListNode head) {
        // 双指针/快慢指针
        ListNode cur=head;
        ListNode prev=head;
        //prev和prev的后一个都不能为空
        while(prev!=null&&prev.next!=null){
            prev=prev.next.next;
            cur=cur.next;
        }
        return cur;
    }


4.链表中倒数第k个结点

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

 题解 :


思路:

1.倒数第k个结点是链表的长度减k再加1.

2.判断特殊情况,head为空,给的k大于链表长度,此时的结果都是null

    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null) {
            return null;
        }
        int len=0;
        ListNode cur=head;
        while(cur!=null) {
            cur=cur.next;
            len++;
        }
        if(k>len) {
            return null;
        }
        int z=len-k;
        cur=head;
        while(z!=0) {
            cur=cur.next;
            z--;
        }
        return cur;
    }


5.合并两个有序链表

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

    题解 :


思路:

1.定义一个头结点,比较两个链表结点的值,进行尾插。

2.当两个链表任意一个到尾时,停止比较,直接将不为零的链表直接加入到我们合并的链表后面。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //判断两个链表是否有空?
        if(list1==null) {
            return list2;
        }
        if(list2==null) {
            return list1;
        }
        //确认头结点
        ListNode head=(list1.val>list2.val)?list2:list1;
        //是头结点,需要向后走一步
        if(head==list1){
            list1=list1.next;
        }else{
            list2=list2.next;
        }
        ListNode cur=head;
        //比较大小,开始尾插
        while(list1!=null&&list2!=null) {
            if(list1.val<=list2.val) {
                cur.next=list1;
                list1=list1.next;
                cur=cur.next;
            }else{
                cur.next=list2;
                list2=list2.next;
                cur=cur.next;
            }
        }
        //插入另一个链表剩余的部分
        cur.next=list1==null?list2:list1;
        return head;
    }
相关文章
|
4天前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
1天前
|
存储 算法 Java
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
25天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
23 1
|
29天前
|
存储 算法 索引
链表面试题
链表面试题
链表面试题
|
11天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
29天前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
29天前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
29天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
29天前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
29天前
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
【一刷《剑指Offer》】面试题 5:从尾到头打印链表