SouthLeetCode-打卡24年01月第5周

SouthLeetCode-打卡24年01月第5周

// Date : 2024/01/39 ~ 2024/01/31

031.删除链表的倒数第 N 个结点

(1) 题目描述

(2) 题解代码

Version1.0

class Solution {
   
    public ListNode removeNthFromEnd(ListNode head, int n) {
   
        if(head == null){
    return null; }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        ListNode stker = head;
        for(int i=0 ; i<n ; i++){
   
            stker = stker.next;
        }
        while(stker != null){
   
            prev = prev.next;
            curr = curr.next;
            stker = stker.next;
        }
        if(curr == null){
   
            prev.next = null;
        }else{
   
            prev.next = curr.next;
        }
        return dummy.next;
    }
}

(3) 题目描述

• Version1.0版本中，实践了无脑思路：1.链表转数组 2.操作数组 3.数组转链表 .

032.相交链表

(1) 题目描述

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

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

(2) 题解代码

public class Solution {
   

    ListNode getIntersectionNodeHelper(ListNode curr1, ListNode curr2,
                                    ListNode head1, ListNode head2){
   
        curr2 = head1;
        while(curr1 != null){
   
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        curr1 = curr2;
        curr2 = head2;
        while(curr1 != curr2){
   
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        return curr1;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
        ListNode currA = headA;
        ListNode currB = headB;
        while(currA != null && currB != null){
   
            currA = currA.next;
            currB = currB.next;
        }
        if(currA != null){
   
            return getIntersectionNodeHelper(currA,currB,headA,headB);
        }else{
   
            return getIntersectionNodeHelper(currB,currA,headB,headA);
        }
    }
}

033.环形链表Ⅱ

(1) 题目描述

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

(2) 题解代码

public class Solution {
   
    public ListNode detectCycle(ListNode head) {
   
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        boolean isCycle  = false;
        while(fast != null){
   
            slow = slow.next;
            fast = fast.next;
            if(fast != null){
   
                fast = fast.next;
                isCycle = fast == slow ? true : false;
            }
            if(isCycle) break;
        }
        if(isCycle){
   
            fast = dummy;
            while(slow != fast){
   
                slow = slow.next;
                fast = fast.next;
            }
        }
        return fast;
    }
}