面试经典150题(55-58)

leetcode 150道题 计划花两个月时候刷完,今天(第二十四天)完成了4道(55-58)150:

55.(19. 删除链表的倒数第 N 个结点)题目描述:

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

第一版(我记得这个有个快慢指针,但是就是不知道咋做,第一版还是求出长度后找出要删除的去删除。)

class Solution {
   
    public ListNode removeNthFromEnd(ListNode head, int n) {
   
        ListNode temp=head;
        int len=0;
        // 求出长度
        while(temp!=null){
   
            len++;
            temp=temp.next;
        }
        // 删除 倒数 第 n 个
        len=len-n;
        ListNode dumpHead=new ListNode(0);
        dumpHead.next=head;
        temp=dumpHead;
        while(temp!=null){
   
            if(len==0&&temp.next!=null){
   
               ListNode remove=temp.next;
               temp.next=remove.next;
               break;
            }
            len--;
            temp=temp.next;
        }
        return dumpHead.next;
    }
}

第二版(快慢指针,给快指针先走 n次 题目里的倒数的 n次,当快指针到最后一个时候,慢指针刚好就是要删除的前一个指针了)

class Solution {
   
    public ListNode removeNthFromEnd(ListNode head, int n) {
   
        ListNode dumpHead=new ListNode(0);
        dumpHead.next=head;

        ListNode low=dumpHead;
        ListNode fast=dumpHead;
        while(fast!=null&&n>0){
   
            n--;
            fast=fast.next;
        }
        while(fast!=null&&fast.next!=null){
   
            fast=fast.next;
            low=low.next;
        }
        if(low.next!=null){
   
            low.next=low.next.next;
        }
        return dumpHead.next;
    }
}

56.(82. 删除排序链表中的重复元素 II)题目描述:

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

第一版(算是模拟出来的。。)

class Solution {
   
    public ListNode deleteDuplicates(ListNode head) {
   
        // 只要是 head 第一个节点可能会被删除,就可以选择新增一个辅助节点避免
        ListNode dumpHead=new ListNode(2000);
        dumpHead.next=head;
        ListNode res=dumpHead;
        ListNode preNode=dumpHead;
        while(res!=null){
   
            if(res.next==null)
                break;
            ListNode temp=res.next;
            while(temp!=null&&temp.val==res.val){
   
                temp=temp.next;
            }
            // 不相等说明当前res节点到temp之前的都要删除的
            if(res.next!=temp){
   
                res.next=temp;
                preNode.next=temp;
            }
            else{
   
                // 记录上一个节点
                preNode=res;
            }
            res=res.next;
            
        }
        return dumpHead.next;
    }
}

57.(61. 旋转链表)题目描述:

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置

第一版(这个其实和第一个差不多,相当于找出来倒数第几个节点,然后截断作为头,连接上原来链表的头)

class Solution {
   
    public ListNode rotateRight(ListNode head, int k) {
   
        ListNode temp=head;
        int len=0;
        ListNode lastNode=head;
        while(temp!=null){
   
            len++;
            lastNode=temp;
            temp=temp.next;
        }
        if(len<=1||k%len==0){
   
            return head;
        }
        k%=len;
        len-=k;
        temp=head;
        for(int i=0;i<len-1;i++){
   
            temp=temp.next;
        }
        ListNode res= temp.next;
        temp.next=null;
        lastNode.next=head;
        return res;
    }
}

58.(86. 分隔链表)题目描述:

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。

第一版(这个我真的想了很久。。虽然写出来了,但是还是一坨,只要你舍得用变量,链表的都还可以)

class Solution {
   
    public ListNode partition(ListNode head, int x) {
   
        ListNode dumpHead=new ListNode(-2000,head);
        ListNode temp=dumpHead;
        ListNode preNode=dumpHead;
        while(temp!=null){
   
            if(temp.val>=x){
   
                break;
            }
            // 这个是记录后面的数据小于x的要插入的头节点
            preNode=temp;
            temp=temp.next;
        }
        // 这个 lastPreNode 是记录下半段的,后面把小于 x 的 节点要放到 
        //第一个PreNode 的前面,导致 链表断开了,所以记录一下再连接起来
        ListNode lastPreNode=preNode;
        while(temp!=null){
   
            ListNode tempNext=temp.next;
            if(temp.val<x){
   
                ListNode next=preNode.next;
                temp.next=next;
                preNode.next=temp;
                preNode=preNode.next;
                lastPreNode.next=tempNext;
            }
            else{
   
                lastPreNode=temp;
            }
            temp=tempNext;
        }
        return dumpHead.next;

    }
}

第二版(看了解题,我感觉我真的是傻逼。。)

class Solution {
   
    public ListNode partition(ListNode head, int x) {
   
        ListNode smallHead=new ListNode(0);
        ListNode smallTemp=smallHead;
        ListNode largeHead=new ListNode(0);
        ListNode largeTemp=largeHead;
        while(head!=null){
   
            if(head.val<x){
   
                smallTemp.next=head;
                smallTemp=smallTemp.next;
            }else{
   
                largeTemp.next=head;
                largeTemp=largeTemp.next;
            }
            head=head.next;
        }
        smallTemp.next=largeHead.next;
        largeTemp.next=null;
        return smallHead.next;
    }
}

链表真的不是我说有点难的。。如果不会了可以多搞几个变量可能会稍微清晰一点。

第二十四天啦!!!为跳好槽而 leetcode !!!

相关推荐

  1. 面试经典150(55-58)

    2023-12-29 12:04:02       56 阅读
  2. 面试经典150(50-53)

    2023-12-29 12:04:02       62 阅读
  3. 面试经典150(59-61)

    2023-12-29 12:04:02       52 阅读
  4. 【leetcode面试经典15056. 基本计算器(C++)

    2023-12-29 12:04:02       32 阅读
  5. 【力扣经典面试55. 跳跃游戏

    2023-12-29 12:04:02       45 阅读
  6. 安卓UI面试 51-55

    2023-12-29 12:04:02       42 阅读
  7. IOS面试编程机制 51-55

    2023-12-29 12:04:02       40 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-29 12:04:02       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-29 12:04:02       106 阅读
  3. 在Django里面运行非项目文件

    2023-12-29 12:04:02       87 阅读
  4. Python语言-面向对象

    2023-12-29 12:04:02       96 阅读

热门阅读

  1. 【数据库】PostgreSQL中的DISTINCT ON和DISTINCT的区别

    2023-12-29 12:04:02       59 阅读
  2. MD5算法

    MD5算法

    2023-12-29 12:04:02      61 阅读
  3. 编程语言的未来?

    2023-12-29 12:04:02       55 阅读
  4. SpringBoot 中实现订单30分钟自动取消的策略

    2023-12-29 12:04:02       60 阅读
  5. Redis使用中的常见问题及解决方案

    2023-12-29 12:04:02       63 阅读
  6. 湘潭大学软件工程头歌多选题-期末考试复习资料

    2023-12-29 12:04:02       59 阅读
  7. MyBatis之配置文件和映射文件

    2023-12-29 12:04:02       47 阅读
  8. MySQL数据库事务

    2023-12-29 12:04:02       51 阅读