首页 > 其他分享 >《剑指offer》day12

《剑指offer》day12

时间:2022-10-17 16:45:35浏览次数:49  
标签:ListNode val offer 复杂度 next day12 l1 null

合并两个排序的链表

题目描述

image

思路

双指针

自己想的,就普通的双指针,结构化讨论

对于第一个节点的确定,自己的思路没问题,提供一种其他思路,用一个伪头节点

代码实现

双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        ListNode result=l1;
        ListNode cur1=l1,cur2=l2;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<=cur2.val){
                while(cur1.next!=null &&cur1.next.val<=cur2.val){
                    cur1=cur1.next;
                }
                ListNode tmp1 = cur1.next,tmp2 = cur2.next;
                cur1.next=cur2;
                cur2.next=tmp1;
                cur2=tmp2;
            }else{
                result=l2;
                while(cur2.next!=null && cur2.next.val<=cur1.val){
                    cur2=cur2.next;
                }
                ListNode tmp2 = cur2.next;
                cur2.next=cur1;
                cur2=tmp2;
            }
        }
        return result;

    }
}

复杂度分析

时间复杂度

O(M+N)

空间复杂度

O(1)

反思不足

思路

对于节点调用next域的时候一定要判断是否为空

两个链表的第一个公共节点

题目描述

image
image
image

思路

正难则反

从尾往头找最后一个相同的节点

需要两次逆置

本题并不行,需要保证原有结构

Set集合

第一个添加失败的节点就是结果

需要哈希表

利用数量关系

遍历A一次后再遍历B一次与反过来遍历的次数是一样的,且公共尾部出现的时机也是一样的

a不等于b,但是a+b会等于b+a,且公共尾部会重合

代码实现

正难则反

Set集合

利用数量关系

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a=headA,b=headB;
        while(a!=b){
            a=a!=null?a.next:headB;
            b=b!=null?b.next:headA;
        }
        return a;
    }
}

复杂度分析

时间复杂度

均为O(M+N)

空间复杂度

哈希表为O(M+N),其他均为O(1)

反思不足

思路

多从数学的量的关系来想题

审题

题目要求不能改变原结构

标签:ListNode,val,offer,复杂度,next,day12,l1,null
From: https://www.cnblogs.com/zhouj-learn/p/16799712.html

相关文章

  • 《剑指offer》day11
    删除链表的节点题目描述思路基本操作代码实现/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*......
  • 剑☞offer 替换空格
    请实现一个函数,把字符串s中的每个空格替换成"%20"。例子:输入:s="Wearehappy."输出:"We%20are%20happy."代码参考点击查看代码classSolution{public:st......
  • 代码随想录 反转字符串(LeetCode 344) ,反转字符串II(LeetCode 541),替换空格(剑指offer
    反转字符串题目编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用......
  • 剑指offer题解
    一,常见数据结构1,数组3-找出数组中重复的数字4-二维数组中的查找5-替换空格29-顺时针打印矩阵leetcode989-数组形式的整数加法leetcode26-删除有序数组中的重复......
  • 《剑指offer》day09
    题目描述思路动态规划+自下而上记录每个元素对应的包含了当前元素的连续和的最大值,最后取一个全局最大的自下而上的话就没有必要保留,一边求一边更新即可递归的话也......
  • java_day12
    Java基础Java集合框架什么是集合?​ 对象的容器,定义了对多个对象进程操作的常用方法。可实现数组的功能。与数组的区别是什么?1.数组长度固定,集合长度是不固定1.数组......
  • 《剑指offer》day08
    斐波那契数列题目描述思路动态规划+哈希表+递归动态规划维基百科定义:动态规划(英语:Dynamicprogramming,简称DP),是一种在数学、管理科学、计算机科学、经济学和生物......
  • 剑指 Offer 05. 替换空格
    请实现一个函数,把字符串 s 中的每个空格替换成"%20"。classSolution{public:stringreplaceSpace(strings){intlen=s.size();intcoun......
  • 剑指offer 38. 字符串的排列
    输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。示例:输入:s="abc"输出:["abc","acb","bac","bca","cab","......
  • 剑指 Offer 22. 链表中倒数第k个节点
    题目描述:输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的......