240419 leetcode exercises-EW帮帮网

240419 leetcode exercises

@jarringslee

文章目录

240419 leetcode exercises

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]

🔁 经典方法：两次遍历暴力求解

我们需要通过第一次遍历获取整个链表的长度L，再通过第二次遍历找到倒数第n个结点的位置，即整数第L - n + 1个结点并进行删除操作——从头开始走 length - n 步，找到要删除节点的“前一个节点”，让这个“前一个节点”的 next 指向要删节点的下一个节点。最后我们返回链表头即可。

//求链表长度的步骤可用函数单独封装
int getlenth(struct ListNode* head){
    int len = 0;
    while (head != NULL){
        len++;
        head = head -> next;//第一次遍历直到结点指针指向空
    }
    return len;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* zhizhen = malloc(sizeof(struct ListNode));
//设置虚拟头结点并进行内存分配以便后续使用
    zhizhen -> val = 0;//虚拟节点不需要用到val值，直接设置为0即可
    zhizhen -> next = head;//虚拟头结点指向真正的头结点

    int len = getlenth(head);
    struct ListNode* now = zhizhen;//用指针开始第二次遍历
    for (int i = 1; i < len - n + 1; i++){
        now = now -> next;//因为第len - n + 1个结点是需要删除的结点，所以我们让虚拟头结点指向它的前一个结点
    }
//前后指针连接，删除指定结点
    now -> next = now -> next -> next;
    struct ListNode* cjx = zhizhen -> next;//用cjx暂存新的头结点（zhizhen->next）
    
    free(zhizhen);
    return cjx; // \释放zhizhen避免内存泄漏，并返回新头节点。
}

🔁 双指针法：快慢指针降低空间复杂度

我们已经通过反向思考知道了倒数第n个结点就是整数第L - n + 1个结点，那么我们如何利用这个发现来在不需要提前知道整个链表的情况下完成查找呢？可以利用快慢指针来进行差值查找。

我们用快指针和慢指针同时对链表进行遍历。快指针先出发，直到遍历到第n个结点的时候慢指针以同样的速度出发，这样快慢指针之间永远间隔了n−1个节点，即超前了n个节点。

当块指针走到尽头时，慢指针刚好指向第L - n 个结点,即倒数第n个结点的前一个结点。利用慢指针即可进行删除操作。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* zhizhen = malloc(sizeof(struct ListNode));
    zhizhen -> val = 0, zhizhen- > next = head;
   
    //插入快慢指针
    struct ListNode* first = head;
    struct ListNode* second = zhizhen;
    //快指针先走n个结点
    for (int i = 0; i < n; ++i) {
        first = first->next;
    }
    //随后慢指针出发 巧妙利用差值找到需要删除的结点的前一个结点
    while (first) {
        first = first->next;
        second = second->next;
    }
    
    second -> next = second -> next -> next;
    struct ListNode* cjx = zhizhen -> next;
    free(zhizhen);
    return cjx;
}

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表由给定两个链表的所有节点拼接而成。

示例 1：
l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
l1 = [], l2 = []
输出：[]
示例 3：
l1 = [], l2 = [0]
输出：[0]

🔁 方法一：迭代法

我们设置一个dummy 来作为新链表的“起点”，并使用一个指针 cur 来记录当前新链表的末尾。每一步我们都比较两个链表当前节点的值，较小的接入新链表，然后对应链表向后移动一格。

遍历结束后，剩余链表（必定是有序的）可以直接接到新链表末尾。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy = {}; // 创建节点，val无所谓
    struct ListNode* cur = &dummy; // cur为新链表的移动指针，初始指向dummy

    // 同时遍历两个链表，每次接入较小值
    while (list1 && list2) {
        if (list1->val < list2->val) {
            cur->next = list1; // list1更小，接入新链表
            list1 = list1->next;
        } else {
            cur->next = list2; // list2更小或相等，接入新链表
            list2 = list2->next;
        }
        cur = cur->next; // 移动cur指针
    }

    // 拼接剩余部分（只会有一个链表剩下）
    cur->next = list1 ? list1 : list2;

    return dummy.next; // 返回新链表的头结点（dummy->next）
}

设置一个虚拟头节点 dummy 可以省去处理头节点的特殊情况；
通过 cur 指针不断拼接较小的节点；
最后直接接上剩余链表即可，整个过程是原地修改，不创建额外节点，效率高。

🔁 方法二：递归法：利用函数栈自动拼接链表

本质思想仍然是“谁小谁先接”，通过递归不断比较当前两个链表的头结点值，较小的那个继续和另一个链表递归合并，直到某个链表为空，返回另一个链表作为终点。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 递归终止条件：有一个链表为空
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    // 递归过程：谁小谁接到前面，并将它的next递归合并
    if (list1->val < list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}```

240419 leetcode exercises