剑指offer题目详细版本(2)

简介: 剑指offer题目详细版本(2)

递归 版本


/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode newHead = null;
        if(list1.val>=list2.val){
            newHead = list2;
            newHead.next = Merge(list1,list2.next);
        }else{
            newHead = list1;
            newHead.next = Merge(list1.next,list2);
        }
        return newHead;
    }
}


4、两个链表的第一个公共结点


///版本一:常规方法
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode node=null;
        int length1=0;
        int length2=0;
        int len=0;
        ListNode ppHead1=pHead1;
        ListNode ppHead2=pHead2;
        while(ppHead1!=null){
            length1++;
            ppHead1=ppHead1.next;
        }
        while(ppHead2!=null){
            length2++;
            ppHead2=ppHead2.next;
        }
        if(length1>=length2){
            len=length1-length2;
            while(len>0){
                pHead1=pHead1.next;
                len--;
            }
        }else if(length1<length2){
            len=length2-length1;
            while(len>0){
                pHead2=pHead2.next;
                len--;
            }
        }
        while(pHead1!=null&&pHead2!=null){
            if(pHead1.val==pHead2.val)
                  return pHead1;
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
        return node;
    }
}
版本二 用Map的containKey()的性质
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        /用HashMap的containKeys的特性
        ListNode currentpHead1=pHead1;
        ListNode currentpHead2=pHead2;
        HashMap<ListNode,Integer> map=new HashMap<ListNode,Integer>();
        while(currentpHead1!=null){
            map.put(currentpHead1,null);
            currentpHead1=currentpHead1.next;
        }
        while(currentpHead2!=null){
            if(map.containsKey(currentpHead2)){
                return currentpHead2;
            }
            currentpHead2=currentpHead2.next;
        }
        return null;
    }
}


/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode node = null;
        if(pHead1==null||pHead2==null){
            return node;
        }
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while(pHead1!=null){
            stack1.push(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null){
            stack2.push(pHead2);
            pHead2=pHead2.next;
        }
        while(!stack1.empty()&&!stack2.empty()){
            if(stack1.peek().val==stack2.peek().val){
                node = stack1.peek();
                stack1.pop();
                stack2.pop();
            }
            else{
                return node;
            }
        }
        return node;
    }
}


5、链表中环的入口结点

6、链表中倒数最后k个结点

7、复杂链表的复制

8、删除链表中重复的结点

9、删除链表的节点

目录
相关文章
|
NoSQL 关系型数据库 MySQL
服了,一线城市的后端都卷成这样了吗!?
工作5年的后端开发工程师,被裁员之后找工作,很难找到,更神奇的事情,我在北京拿到了两个offer,但是深圳一个都没拿到,我更倾向在深圳找工作,实在没办法才会去北京。而且深圳这边的工作很卷,考察的越来越难,不仅是八股,不少公司更多的事考察场景题,甚至还有公司问我如果让我带一个5~10人小团队做项目会考虑哪些事情?天啊,我只是一个想找20K工作的gopher程序员,要求已经这么高了吗?太卷了。
147 3
|
存储 人工智能 Java
Unity优化——脚本优化策略4
Unity优化——脚本优化策略4
209 0
|
9月前
|
存储 小程序 Python
农历节日倒计时:基于Python的公历与农历日期转换及节日查询小程序
### 农历节日倒计时:基于Python的公历与农历日期转换及节日查询小程序 该程序通过`lunardate`库实现公历与农历的日期转换,支持闰月和跨年处理,用户输入农历节日名称后,可准确计算距离该节日还有多少天。功能包括农历节日查询、倒计时计算等。欢迎使用! (239字符)
473 86
|
11月前
|
SQL
高频SQL50题(基础版)二
高频SQL50题(基础版)二
|
Java
JAVA生产随机生成验证码
Java代码实现随机生成指定位数的数字、大小写字母混合的验证码。使用`Random`类生成类型(0-数字,1-大写字母,2-小写字母),然后根据类型转换为相应字符。示例代码展示了一个4位验证码的生成,并附有实现结果图和过程分析。
358 2
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
134 0
|
SQL Java 数据库连接
动态表后缀
动态表后缀
|
搜索推荐
排序进行曲-v1.0
排序进行曲-v1.0
|
前端开发 JavaScript API
前端开发:Promise详解
做过前端开发的都知道,JavaScript是单线程语言,浏览器只分配给JS一个主线程,用来执行任务,但是每次一次只能执行一个任务,这些任务形成一个任务队列排队等候执行;但是某些任务是比较耗时的,如网络请求,事件的监听,以及定时器,如果让这些非常耗时的任务一一排队等候执行,那么程序执行效率会非常的低,甚至会导致页面假死。
554 1
前端开发:Promise详解
|
存储 数据挖掘 开发者
微信小游戏推广运营专业术语汇总
本文内容包括与微信小游戏运营推广相关的专业术语的汇总和解释。作为一个游戏开发者,不光要知道如何做游戏,也要知道如何让别人玩自己做的游戏。 如果你没有任何的游戏开发经验,欢迎阅读我的“人人都能做游戏”系列教程,它会手把手的教你做出自己的第一个小游戏。
297 0