桃桃摇摇奶昔° 普通 2024年11月21日下午2:18

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

时间复杂度O（n），空间复杂度O（1）

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode f = head;
        ListNode s = head;
        // 让快指针到第ctn个节点
        for (int i = 0; i < cnt; i++) {
            f = f.next;
        }
        while (f != null) {
            f = f.next;
            s = s.next;
        }
        return s;
    }
}

mpweixin用户普通 2024年11月21日下午2:08

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

解题思路
本题可以采用双指针迭代的思路来解决。首先创建一个虚拟头节点（哨兵节点），这样可以统一处理链表头部的逻辑。然后使用两个指针分别遍历两个链表，比较当前两个指针指向的节点值的大小，将较小的节点接入新链表中，并将对应的指针向后移动。这个过程就像是对两串项链进行归并，每次都选择数值较小的珠子串接到新链表上。
当其中一个链表遍历完成后，我们只需要将另一个链表的剩余部分直接接到新链表的末尾即可。这是因为输入的两个链表本身就是有序的，所以未遍历完的部分一定大于已经合并的所有节点，并且它们本身保持着有序性。

复杂度分析
时间复杂度：O(n + m)，其中n和m分别是两个链表的长度。我们需要遍历两个链表各一次。
空间复杂度：O(1)，只使用了常数个指针变量，没有使用额外的空间。

代码实现

“`c++
class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
// 创建哨兵节点，简化头节点的处理逻辑
ListNode* merge = new ListNode(0);
ListNode* temp = merge;

    // 当两个链表都非空时，比较节点值并合并
    while (l1 && l2) {
        if (l1->val < l2->val) {
            temp->next = l1;
            l1 = l1->next;
        } else {
            temp->next = l2;
            l2 = l2->next;
        }
        temp = temp->next;
    }

    // 将未遍历完的链表直接接到结果链表末尾
    temp->next = l1 == nullptr ? l2 : l1;

    // 返回合并后的链表（跳过哨兵节点）
    return merge->next;
}

};

桃桃摇摇奶昔° 普通 2024年11月21日下午1:59

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head.valval){return head.next;}
if (headnull){return null;}
ListNode p = head;
ListNode temp = head.next;
while(temp != null){
if (temp.val val){
p.next=temp.next;
return head;
}
temp=temp.next;
p=p.next;
}
return head;
}
}
时间复杂度O（n），空间复杂度：O(1) —— 仅使用了常数额外空间。

Renasc 普通 2024年11月21日下午1:48

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

50+
没有
不是很懂

Renasc 普通 2024年11月21日下午1:47

本打卡对应问题：【阅读补充】时间/空间复杂度如何计算？
具体打卡内容：

打卡

Renasc 普通 2024年11月21日下午1:41

本打卡对应问题：【链表专题】剑指 Offer 52. 两个链表的第一个公共点
具体打卡内容：

时间复杂度O(n)，空间复杂度O(1)

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果有一个为null，就返回null
        if (headA == null || headB == null) {
            return null;
        }

        ListNode A = headA, B = headB;

        // 遍历双指针
        while (A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }

        return A;
    }
}

zing 普通 2024年11月21日下午1:30

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

为什么在判断链表是否为空时是判断 while index1，而不是while index.next

class Solution:
    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        index1, index2 = l1, l2
        ans = ListNode(0, None)
        bummy = ans

        while index1 and index2:
            if index1.val > index2.val:
                bummy.next = index2

                index2 = index2.next
            else:
                bummy.next = index1

                index1 = index1.next
            bummy = bummy.next

        if index1:
            bummy.next = index1
        elif index2:
            bummy.next = index2

        return ans.next

Pendulumpal 普通 2024年11月21日下午12:22

本打卡对应问题：【链表专题】剑指 Offer 52. 两个链表的第一个公共点
具体打卡内容：

用集合记录headA链表所有节点的地址
遍历headB,找到其中第一个存在于st的地址返回
T O(n), M O(m),m为headA链表长度

“`c++
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set st;
while(headA){
st.insert(headA);
headA=headA->next;
}
while(headB){
if(st.count(headB)){
return headB;
}
headB=headB->next;
}
return nullptr;
}
“`

捕风永久会员 2024年11月21日下午12:20

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

/**
* 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 deleteNode(ListNode head, int val) {
//先解决特殊情况：是否为空指针、是否为头节点
//如果遍历到空指针
if(head null){
return null;
}

//如果删除的是头节点
if(head.val == val){
    return head.next;
}

ListNode temp = head.next; //temp表示要删除的结点
ListNode pre = head; //pre永远指向temp 的前一个节点，用于修改链表指针以删除目标节点

while(temp != null){
    // 如果找到，直接删除，返回
    if(temp.val == val){
        pre.next = temp.next;
        return head;
    }
    temp = temp.next; // 如果没有找到，继续下一个
    pre = pre.next;
}

return head;

}

}
时间复杂度：O(n) —— 最多遍历链表中的 n 个节点。
空间复杂度：O(1) —— 仅使用了常数额外空间。

Tom Yuan 普通 2024年11月21日下午12:14

本打卡对应问题：【链表专题】剑指 Offer 52. 两个链表的第一个公共点
具体打卡内容：

从各自的起点出发寻找相同的节点如果有任意一个走完了还找不到就指向第二个继续找直到二者全部走完
有一种构造了环的感觉但实际上又不是环在某个时间节点将两个链表连接了起来

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None

        a = headA
        b = headB
        while a != b:
            # connect back to the other LL
            # if reached anyone's end but still didn't find.
            a = a.next if a else headB
            b = b.next if b else headA

        return a

time: O(m+n)
space: O(1)

zing 普通 2024年11月21日下午12:01

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

设置虚拟头结点

class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        fast = slow = dummy.next
        for i in range(cnt-1):
            fast = fast.next

        while fast.next:
            fast = fast.next
            slow = slow.next
        return slow

陆狗陆狗普通 2024年11月21日上午11:46

本打卡对应问题：什么是时间复杂度？
具体打卡内容：

牛批

Renasc 普通 2024年11月21日上午11:45

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

时间复杂度 O(n), 空间复杂度O(1)

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        // 建立虚拟头结点
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        // 合并左右链表
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        // 将剩下的链表接上
        curr.next = (l1 != null) ? l1 :l2;

        // 返回头结点
        return dummy.next;
    }

}

陆狗陆狗普通 2024年11月21日上午11:38

本打卡对应问题：【阅读补充】时间/空间复杂度如何计算？
具体打卡内容：

打卡学习

zing 普通 2024年11月21日上午11:37

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

链表结点的思考：
链表结点包含两个域，一个数据域一个指针域。其中指针域在代码实现时保存的是下一个结点，来实现“指针”的功能。

Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

解法一：需考虑边界条件

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val  val: return head.next
        pre, cur = head, head.next
        while cur and cur.val != val:
            pre, cur = cur, cur.next
        if cur: pre.next = cur.next
        return head

解法二：设置头结点，一般化

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head == None:    return head
        dummy = ListNode(0, head)

        pre, cur = dummy, dummy.next
        while cur and cur.val != val:
            pre, cur = cur, cur.next
        if cur: 
            pre.next = cur.next
        return dummy.next

陆狗陆狗普通 2024年11月21日上午11:33

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

1.10几个
2.没有
3.完全不会

Rad 普通 2024年11月21日上午11:15

本打卡对应问题：【链表专题】剑指 Offer 52. 两个链表的第一个公共点
具体打卡内容：

时间复杂度O（m+n）
空间复杂度O1
/**
* 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) {
if(headA null) return null;
if(headB null) return null;
ListNode A = headA;
ListNode B = headB;

    while (A != B){
        if (A != null){
            A = A.next;
        }
        else A = headB;
        if (B != null){
            B = B.next;
        }
        else B = headA;
    }
    return A;

}

}

Tom Yuan 普通 2024年11月21日上午10:56

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

双指针先建立一个新的LL 拿到头然后位于两个链表上的指针比较值大小小的就往新的list上塞
随后如果一个走完了另一个还没走完说明另一个剩下的都比走完的所有值大然后将其拼接到结果上

因为一开始创建了一个特殊值的头节点0 取结果时记得把他扣掉

def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        new_start = ListNode(0)
        cur = new_start

        while l1 != None and l2 != None:
            if l1.val > l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1
                l1 = l1.next
            cur = cur.next

        if l1 == None:
            cur.next = l2
        else:
            cur.next = l1

        return new_start.next

time: O(m+n)
space: O(1) 头节点剩余的都是建立的next

C。普通 2024年11月21日上午10:48

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

思路

ListNode merge = new ListNode(0);
ListNode temp = merge;//防止空指针异常
创建临时节点，比较L1,L2的值，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 trainningPlan(ListNode l1, ListNode l2) {
ListNode merge = new ListNode(0);
ListNode temp = merge;

    while(l1 != null && l2 != null){
        if(l1.val < l2.val){

            temp.next = l1;
            l1 = l1.next;
        } else {
            temp.next = l2;
            l2 = l2.next;
        }

        temp = temp.next;
    }

    temp.next = l1 == null ? l2 : l1;

    return merge.next;
}

}
时间复杂度O（m+n）
空间复杂度O（1）

Renasc 普通 2024年11月21日上午10:40

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        if (head == null && head.next == null) {
            return head;
        }

        // 设置虚拟头结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 设置快慢指针
        ListNode fast = dummy.next;
        ListNode slow = dummy.next;

        // 先让快指针走cnt步
        for (int i=0; i<cnt; i++) {
            fast = fast.next;
        }

        // 让快慢指针一起走，等快指针结束，慢指针就到了倒数第cnt个位置
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

jaron 普通 2024年11月21日上午10:37

本打卡对应问题：【阅读补充】时间/空间复杂度如何计算？
具体打卡内容：

打卡

Rad 普通 2024年11月21日上午10:37

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

/**
* 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 trainningPlan(ListNode l1, ListNode l2) {
if (l1 null){return l2;}
if (l2 null){return l1;}
ListNode head;
if(l1.val <= l2.val){
head = l1;
l1 = l1.next;
}
else {
head = l2;
l2 = l2.next;
}
ListNode node = head;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
node.next = l1;
l1 = l1.next;
}
else{
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
node.next = l1 null? l2:l1;
return head;
}
}
时间复杂度O（m+n）
空间复杂度O（1）

jaron 普通 2024年11月21日上午10:37

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

1.100+
2.刷过几题
3.回溯并查集不太懂

mpweixin用户普通 2024年11月21日上午10:34

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

解题思路：

这道题可以巧妙地使用快慢指针来解决。解题的核心思想是让一个快指针先走cnt步，然后快慢指针再同时前进。这样当快指针到达链表末尾时，慢指针正好位于倒数第cnt个节点。这是因为快慢指针之间始终保持着cnt个节点的距离，当快指针走到末尾，慢指针自然就处于倒数第cnt个位置。

具体来说，我们首先让快指针从头节点开始向前移动cnt步。这个过程中需要注意检查快指针是否为空，如果为空说明链表长度小于cnt，此时应该返回空。当快指针移动完cnt步后，我们开始同时移动快慢指针，直到快指针到达链表末尾。此时慢指针指向的就是我们要找的倒数第cnt个节点。

时空复杂度：

时间复杂度：O(n)，其中n为链表的长度。虽然使用了快慢指针，但实际上只需要遍历一次链表就能得到结果。空间复杂度：O(1)，只使用了两个指针变量，所需额外空间固定。

代码实现：

“`C++
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
// 处理空链表的边界情况
if(head == nullptr) return nullptr;
ListNode* fast = head;
ListNode* slow = head;

    // 让快指针先走cnt步
    for(int i = 0;i<cnt;i++){
        if(fast == nullptr){
            return nullptr;  // 链表长度小于cnt的情况
        }
        fast = fast->next;
    }

    // 快慢指针同时移动，直到快指针到达末尾
    while(fast != nullptr){
        fast = fast->next;
        slow = slow->next;
    }
    // 此时slow指向倒数第cnt个节点
    return slow;
}

};

“`

jaron 普通 2024年11月21日上午10:29

本打卡对应问题：【链表专题】剑指 Offer 52. 两个链表的第一个公共点
具体打卡内容：

时间复杂度：O(n+m)，n 和 m 表示两个链表长度
空间复杂度：O(1)

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        while (a != b){
            // 走到null就回到另一个链表开头
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

Rad 普通 2024年11月21日上午10:21

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

/**
* 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 trainingPlan(ListNode head, int cnt) {
if(head null){return null;}
ListNode first = head;
ListNode second = head;
for(int i=0;i<cnt;i++){
first = first.next;}
while(first != null){
first = first.next;
second = second.next;
}
return second;

}
时间复杂度On
空间复杂度O1

jaron 普通 2024年11月21日上午10:13

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

时间复杂度：O(n+m)，n 和 m 表示两个链表长度
空间复杂度：O(1)

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        // 确定头结点
        ListNode head;
        if (l1.val <= l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        ListNode cur = head;
        // 选择较小的接上
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 若果一个搞完了，直接把另一个剩下的全部接上
        cur.next = l1 == null ? l2 : l1;
        return head;
    }
}

Renasc 普通 2024年11月21日上午10:11

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

通过设置虚拟头结点来进行遍历

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = dummy.next;

        while (curr != null) {
            if (curr.val == val) {
                    prev.next = curr.next;
            }
            prev = curr;
            curr = curr.next;
        }
        return dummy.next;
    }
}

Tom Yuan 普通 2024年11月21日上午10:06

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

快慢指针都从头开始一个提前走k步当先走的那个到达结尾后的null 后走的就是结果

class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        # the first pointer is where it lands at cnt
        # when the second pointer reaches the end
        first = head
        second = head
        for i in range(cnt):
            if second == None:
                # the list is shorter than cnt
                return None
            second = second.next

        while second != None:
            first = first.next
            second = second.next

        return first

有个注意的点是先开始走的时候的判断条件如果先走的点本身已经变成null了那么就可以停下输出null了而不是判断他的下一个
判断下一个是null的话可能会出现越过了最后一个点的情况。

time: O(n) 前半段O(k) 后半段O(n – k)
space: O(1) 两个指针

mpweixin用户普通 2024年11月21日上午10:04

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

1 200+，但感觉没有真正理解
2.跟着帅地网站刷过一遍
3.并查集不懂

mpweixin用户普通 2024年11月21日上午10:03

本打卡对应问题：【链表专题】剑指 Offer 52. 两个链表的第一个公共点
具体打卡内容：

“`C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr) return nullptr;
ListNode* n1 = headA;
ListNode* n2 = headB;
while(n1!=n2){
if(n1!=nullptr){
n1 = n1->next;
}else{
n1 = headB;
}
if(n2!=nullptr){
n2 = n2->next;
}else{
n2 = headA;
}
}
return n1;
}
};
“`
打卡

吃碗草莓豆沙普通 2024年11月21日上午9:42

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

1.几道
2.没有
3.有部分了解

Tom Yuan 普通 2024年11月21日上午9:38

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

前后指针的思路后一个摸到了那么把前一个的next指向后一个的next 来抠掉需要删除的node（第一次发错版了）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteNode(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:

        # return null if head null
        if head == None:
            return None

        # handle found at head
        if head.val == val:
            head = head.next
            return head

        # handle else
        # if at last, then set to null (last.next)
        first = head
        second = head.next
        while first.next != None:
            if second.val == val:
                first.next = second.next
                return head
            first = first.next
            second = second.next

mpweixin用户普通 2024年11月21日上午9:37

本打卡对应问题：【链表专题】剑指 Offer 25. 合并两个排序的链表
具体打卡内容：

打卡
”’c++

/**
* Definition for singly-linked list.
* 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 trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* dum = new ListNode(-1);
ListNode* res = dum;
while(l1 && l2){
if(l1->valval){
res->next = l1;
l1 = l1->next;
}else{
res->next = l2;
l2 = l2->next;
}
res = res->next;
}
if(l1){
res->next = l1;
}
if(l2){
res->next = l2;
}
return dum->next;

};

”’

Tom Yuan 普通 2024年11月21日上午9:36

本打卡对应问题：剑指 Offer 18. 删除链表的节点
具体打卡内容：

前后指针的思路后一个摸到了那么把前一个的next指向后一个的next 来抠掉需要删除的node

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteNode(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:

        # return null if head null
        if head == None:
            return None

        # handle found at head
        if head.val == val:
            head = head.next
            return head

        # handle else
        # if at last, then set to null (last.next)
        first = head
        second = head.next
        while first.next != None:
            if second.val == val:
                first.next = second.next
                return head
            first = first.next
            second = second.next

mpweixin用户普通 2024年11月21日上午9:23

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

打卡

“`c++
/**
* Definition for singly-linked list.
* 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* trainingPlan(ListNode* head, int cnt) {
ListNode* fast = head;
ListNode* slow = head;
if(head == nullptr){
return nullptr;
}
while(cnt–){
fast = fast->next;
}
while(fast!=nullptr){
fast = fast->next;
slow = slow->next;
}
return slow;

};

“`

mpweixin用户普通 2024年11月21日上午9:22

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

题解思路：
本题的要求是从链表中删除特定值的节点。为了简化操作，我们可以引入一个虚拟的头节点，把它指向真实的链表头。这样，无论删除的是头节点还是其他节点，我们都可以从虚拟头节点开始遍历。
在遍历过程中，我们使用一个指针检查每个节点的下一个节点的值。如果该值等于目标值，我们就调整当前节点的 next 指针，跳过要删除的节点。否则，我们将指针移动到下一个节点，继续检查。
遍历结束后，新链表的头节点是虚拟头节点的 next 指针所指向的节点。
最后，别忘了释放虚拟头节点的内存。

参考代码：

“`c++
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
// 创建一个虚拟头节点，用于处理删除头节点的情况
ListNode* dummyHead = new ListNode();
dummyHead->next = head;

    // 当前节点初始化为虚拟头节点
    ListNode* cur = dummyHead;

    // 遍历链表，直到当前节点的下一个节点为空
    while (cur->next != nullptr) {
        // 如果下一个节点的值等于要删除的值
        if (cur->next->val == val) {
            // 通过跳过下一个节点来删除它
            cur->next = cur->next->next;
        } else {
            // 如果值不等于，继续移动到下一个节点
            cur = cur->next;
        }
    }

    // 获取新的头节点（即删除操作后的链表头）
    ListNode* newHead = dummyHead->next;
    // 释放虚拟头节点的内存
    delete dummyHead;
    // 返回新的链表头
    return newHead;
}

};

“`

时空分析：
首先，时间复杂度方面，由于我们需要遍历链表中的每个节点一次，检查并删除符合条件的节点。因此，时间复杂度为 O(n)，其中 n 是链表中节点的总数。这是因为我们可能需要对每个节点进行一次访问。
其次，空间复杂度方面，我们使用了一个虚拟头节点来帮助处理删除操作，但这个虚拟节点的空间消耗是常量级的。除了指针外，没有使用额外的空间来存储其他数据。因此，空间复杂度为 O(1)。
综上所述，该算法的时间复杂度是 O(n)，而空间复杂度是 O(1)。

🌟 普通 2024年11月21日上午9:15

本打卡对应问题：【链表专题】剑指 Offer 52. 两个链表的第一个公共点
具体打卡内容：

好
class Solution {
public:
ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA||!headB) return nullptr;
ListNode A=headA;
ListNode* B=headB;
while(!(!A&&!B)){
A=A?A->next:headB;
B=B?B->next:headA;
if(AB) return A;
}
return nullptr;

};

mpweixin用户普通 2024年11月21日上午9:14

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

打卡

“`c++
/**
* Definition for singly-linked list.
* 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* deleteNode(ListNode* head, int val) {
if(head == nullptr){
return nullptr;
}
if(head->val == val){
return head->next;
}
ListNode* node = head->next;
ListNode* pre = head;
while(node !=nullptr){
if(node->val == val){
pre->next = node->next;
return head;
}
node = node->next;
pre = pre->next;

    }

return head;

}


};
“`

jaron 普通 2024年11月21日上午9:10

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

时间复杂度O(n)
空间复杂度O(1)

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode temp = head;
        for (int i = 0; i < cnt; i++) {
            if (temp == null) {
                return null;
            }
            temp = temp.next;
        }
        while (temp != null) {
            temp = temp.next;
            head = head.next;
        }
        return head;
    }
}

jaron 普通 2024年11月21日上午8:52

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

时间复杂度O(n)
空间复杂度O(1)

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode last = head;
        ListNode cur = null;
        while (last.next != null) {
            cur = last.next;
            if (cur.val == val) {
                last.next = cur.next;
                break;
            }
            last = cur;
        }
        return head;
    }
}

mpweixin用户普通 2024年11月21日上午6:45

本打卡对应问题：【阅读补充】时间/空间复杂度如何计算？
具体打卡内容：

时间复杂度是用来衡量算法的运行时间，关注输入规模对于时间的影响，通常通过分析算法中的循环和递归来确定。
例如：
对于一个简单的循环，从 1 到 n 迭代，时间复杂度是 O(n)。
嵌套循环，比如一个循环从 1 到 n，另一个循环也从 1 到 n，时间复杂度是 O(n²)。
空间复杂度则是衡量算法的内存使用，关注输入规模对内存的影响。
主要是分析算法中使用的额外变量、数组、对象等所消耗的内存
例如：
如果使用了一个长度为 n 的数组，空间复杂度是 O(n)。
如果只用了固定数量的变量，空间复杂度是 O(1)。

mpweixin用户普通 2024年11月21日上午6:40

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

1、leetcode刷过几道题了？
200+
2、剑指offer 之前学过吗？
没有
3、贪心，回溯，动态规划，并查集懂吗？
基本懂

土豆哥普通 2024年11月21日上午2:35

本打卡对应问题：【阅读补充】时间/空间复杂度如何计算？
具体打卡内容：

打

土豆哥普通 2024年11月21日上午2:33

本打卡对应问题：【链表专题】剑指 Offer 22. 链表中倒数第k个节点
具体打卡内容：

“`java
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
ListNode former = head, latter = head;
for(int i=0;iwhile(former!=null) { former = former.next; latter = latter.next; } return latter; }

}

mpweixin用户普通 2024年11月21日上午2:07

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

“`java
18.删除链表的节点
class Solution {
public ListNode deleteNode(ListNode head, int val) {

    if(head==null) return null;
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode cur = dummy;
    while(cur.next!=null){
        if(cur.next.val ==val){
            cur.next = cur.next.next;
            break;
        }
        else cur = cur.next;
    }
    return dummy.next;

}
}

mpweixin用户普通 2024年11月21日上午1:54

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

1.50题
2.没有学过
3.不是很懂

張叁普通 2024年11月21日上午1:53

本打卡对应问题：【测一测你的算法】你目前算法都学过啥？
具体打卡内容：

1、leetcode刷过几道题了？
三题
2、剑指offer 之前学过吗？
没有
3、贪心，回溯，动态规划，并查集懂吗？
听过名字

Rad 普通 2024年11月21日上午1:26

本打卡对应问题：【链表专题】剑指 Offer 18. 删除链表的节点
具体打卡内容：

/**
* 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 deleteNode(ListNode head, int val) {
if (head null){
return null;
}
if (head.val val){
return head.next;
}

    ListNode temp = head.next;
    ListNode pre = head;

    while(temp != null){
        if(temp.val == val){
            pre.next = temp.next;
            return head;
        }
        temp = temp.next;
        pre = pre.next;

    }
    return head;
}

}
时间复杂度O（n）
空间复杂度O（1）

Rad 普通 2024年11月21日上午1:00

本打卡对应问题：【阅读补充】时间/空间复杂度如何计算？
具体打卡内容：

打