每日1+1题(链表相交、环形链表)+java学习

面试题 02.07. 链表相交

同：160.链表相交

力扣题目链接(opens new window)

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

示例 2：

示例 3：

142.环形链表II

力扣题目链接(opens new window)

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

//面试题 02.07. 链表相交
// Created by 徐昊岩 on 2023/10/20.
//思考的过程确实需要灵感，99%的题目都不是能机械证明的，或许灵感可以依靠经验得来的诱导性思维?
//不如说，一切难题在第一次求解之前都是非机械证明的过程
//目前有什么(观察)，目前需要什么(目的导向)，你可以改变什么(有什么得来)

//环形链表
//通过上述的诱导性思维，确实得出了一种空间复杂度为O(1)的算法，但是时间超过了(nm
//定量分析？只能说这之间可能存在着数量关系，然后你去研究一下，发现确实有数量关系，然后才能写出相应算法
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pa = headA;
        ListNode *pb = headB;
        int count_a = 0, count_b = 0;
        int i=0;
        while (pa) {
            count_a++;
            pa = pa->next;
        }
        while (pb) {
            count_b++;
            pb = pb->next;
        }
        pa=headA;
        pb=headB;
        if (count_a > count_b) {
            for (i = 0; i < count_a - count_b; i++) pa = pa->next;
            for (i = 0; i < count_b; i++) {
                if (pa == pb) return pa;
                pa = pa->next;
                pb = pb->next;
            }
        } else {
            for (i = 0; i < count_b - count_a; i++) pb = pb->next;
            for (i = 0; i < count_a; i++) {
                if (pa == pb) return pa;
                pa = pa->next;
                pb = pb->next;
            }

        }
        return nullptr;
    }
};

class Solution2 {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast=head;
        ListNode *slow=head;
        int count=0;
        int flag=0;
        while (fast && fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2;
            }
        }
        return nullptr;

    }
};

java学习

String

在Java中，String是一个引用类型，它本身也是一个class。但是，Java编译器对String有特殊处理，即可以直接用"..."来表示一个字符串：

String s1 = "Hello!";

实际上字符串在String内部是通过一个char[]数组表示的，因此，按下面的写法也是可以的：

String s2 = new String(new char[] {'H', 'e', 'l', 'l', 'o', '!'});

因为String太常用了，所以Java提供了"..."这种字符串字面量表示方法。

Java字符串的一个重要特点就是字符串不可变。这种不可变性是通过内部的private final char[]字段，以及没有任何修改char[]的方法实现的