LeetCode刷题日记

LeetCode刷题日记

一、链表类 1、LeetCode第21题（合并两个有序链表）【简单】

// 解法一：双指针拉链法，比较当前指针位所在值的大小，若比较a1和a2时a1>=a2，直接将a2的指针指向a1依次类推
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 定义新链表
        ListNode temp=new ListNode(-1);
        // 定义头指针
        ListNode p=temp;
        ListNode p1=list1;// 自己能点出来的，直接赋值就好
        ListNode p2=list2;
        while(p1!=null && p2!=null){
            if(p1.val<p2.val){
                p.next=p1;
                p1=p1.next;
            }else{
                p.next=p2;
                p2=p2.next;
            }
            p=p.next;
        }
        if(p1!=null){
            p.next=p1;
        }
        if(p2!=null){
            p.next=p2;
        }
        return temp.next;
    }
}







// 二刷：心得=》必要时一定要定义一个辅助指针，需要一个始终不表的头指针来链接上所有的数据
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1.定义一个虚拟头指针（新的链表），目的存放合并完成的链表
        ListNode temp=new ListNode(-1);
        // 需要一个一直在移动的指针，一个不动的头指针
        ListNode dummy=temp;
        // 2.分别给两个链表定义头指针
        ListNode p1=list1;
        ListNode p2=list2;
        // 3.循环拉拉链
        while(p1!=null&&p2!=null){
            if(p1.val<=p2.val){
                // 链到新链表后面
                dummy.next=p1;
                // 后移
                p1=p1.next;
            }else{
                dummy.next=p2;
                p2=p2.next;
            }
            dummy=dummy.next;
        }
        // 4.判断最后一个值的位置
        if(p1!=null){
            dummy.next=p1;
        }
        if(p2!=null){
            dummy.next=p2;
        }
        return temp.next;
    }
}

2、LeetCode第141题（环形链表【判断是否为环形链表】）【简单】

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
       // 使用快慢指针，再环形链表中必会相交的特点来判断
       // 1.定义快慢指针
       ListNode fast=head;
       ListNode slow=head;
       // 2.(退出循环的条件，一快指针已经null没环；相遇满足成环条件)
       while(fast!=null&&fast.next!=null){
           fast=fast.next.next;
           slow=slow.next;
           // 每次走完判断
           if(fast==slow){
               return true;
           }
       }
       return false;
    }
}

3、LeetCode第141题目（判断环形链表交点位置）【中等】

分析：

1、按照套圈问题总结，fast一定是slow的2k倍

2、设slow到相遇点时为k，那么fast为2k

3、设环形起点到相遇点是m=》那么head到环形起点位置为=k-m（slow那一块）

4、那么按照这样计算=》fast的角度出发就是（head到环形起点位置为=2k-k-m）

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
// 交点处，无非就是走完前面一小段到环的位置的地方（如图就是3=》2这段距离）
// 难点解出这段距离的长度
// 使用快慢指针，当相遇时，将任何一个指针返回到头节点，然后再两一个一起走，那么再次相遇的时候，就是目标
// 在代码中指针定义走两倍之差
// 思路如图：假设一个相遇点，想象一下从相遇点截断甩到头头指针位置就是这段目标距离
        // 1.定义快慢指针
        ListNode fast=head;
        ListNode slow=head;
        // 2.执行快慢指针的常规 *** 作
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            // 2.1找到相遇点跳出循环
            if(slow==fast){
                slow=head;
                break;
            }
        }
        // 注意判断不成环的情况
        if(fast==null||fast.next==null){
            return null;
        }
        // 3.这个时候就一步一步走了,当他们再次相遇时跳出循环
        // 3.1记录链表的索引下标位置
        int count = 0;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
            count ++;
        }
        System.out.println("index："+count);
        return slow;
    }
}

4、LeetCode第876题（链表中间节点）【简单】

// 解法一：计算链表的长度后，size/2得中间得位置即可

// 解法二：使用快慢指针的技巧（当速度是两倍的快指针到尾部时，慢指针刚好到中间）
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        // 使用快慢指针，快指针一次走两步，慢指针一次走一步
        // 1、定义快慢指针
        ListNode fast=head;
        ListNode slow=head;
        // 2.遍历
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

5、LeetCode第160题（相交链表）【简单】

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

如果两个链表不存在相交节点，返回 null 。

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

解法分析：

这种解法就是将指针遍历到等长的位置找到对应的交点；

// 解法一：化为等长的链表去找交点
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 概述：找到交点，问题是如何定位
        // 难点：两个长度不一样的链表如何将长度变为一样，定位到交点
        // 使用双指针，当两个指针到到达末尾时，马上让他们指向另一个链表，当相交时到交点
        // 1.定义双指针
        ListNode p1=headA;
        ListNode p2=headB;
        // 2.遍历
        while(p1!=p2){
            // 2.1判断是后移还是当一个指针到null就指向另一条链表
            if(p1==null){
                p1=headB;
            }else{ 
                 p1=p1.next;
            }
            if(p2==null){
                p2=headA;
            }else{
                p2=p2.next;  
            }
        }
        return p1;
    }
}

6、LeetCode第19题（删除倒数第n个节点）【中等】

// 法一：遍历找到目标节点，再遍历一边删除

// 难点：1、遍历一次就拿捏它；2、控制虚拟头节点的恰当使用，避免NPE

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
// 概述：删除倒数第n个节点；就是删除正数第【总长-（n-1）】个节点
// 使用虚假节点和双指针技巧（遍历一次）解决
// 快指针先走n步；然后慢指针再走=》当快指针走到末尾，那么慢指针删除正数第【总长-（n-1）】个节点
        // 使用虚假指针避免空指针
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        // 1.定义快慢指针
        ListNode fast=dummy;
        ListNode slow=dummy;
        // 3.快指针先走n步(这里走n-1步是为了找到目标接节点的前一个节点，便于删除目标节点)
        // 可以考虑封装一个方法，去找到对应的节点
        for(int i=0;i<n+1;i++){
            fast=fast.next;
        }
        // 4.慢指针和快指针同时开始走
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }
}

7、LeetCode第23题（合并K个升序链表）【困难】==》2022.03.27 23:50 待解决；需要使用更高级的算法和数据结构，学完基础再干