算法刷题目链表

2023-10-11

Source

Edit

History

两个单链表生成相加链表

一、题目

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

1 2	输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912

算法刷题目链表

2023-10-11

Source

Edit

History

删除链表的中间节点

一、题目

给你一个链表的头节点 head 。删除链表的中间节点，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

leetcode：https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/

二、思路

当长度为1 时，不删除；长度为 2 时，删除第1 个节点；长度为3时，删除第 1 个节点；长度为 4 时，删除第 2 个节点；长度为 5 时，删除第 2 个节点。(下标以 0 开始)

算法刷题目链表

2023-10-11

Source

Edit

History

合并K个升序链表

一、题目

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

Leetcode：https://leetcode.cn/problems/merge-k-sorted-lists/

二、分析

我们准备一个优先级队列，也就是一个堆，并且是一个最小堆。长度为 K。也就是将 K 个链表的头节点插入堆中。

算法刷题目链表

2023-10-11

Source

Edit

History

判断一个链表是否为回文结构

一、题目

给定一个链表的头节点 head，请判断该链表是否为回文结构。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

leetcode：https://leetcode.cn/problems/aMhZSa/

二、思路

我们可以使用栈的性质来做，将链表中的元素插入到栈中。栈有先进后出的性质，所以当把所有元素插入进去之后，从栈中依次取出来的元素顺序就是从链表的尾部向头部遍历的过程。在和原链表进行比对即可。这是第一种思路。

如上的这种思路还有可以优化的余地，我们不用插入链表中所有的元素，我们只需要插入链表中一半的元素即可。并且插入链表的后半部分。如果链表的长度是奇数，那就忽略最中间的那个元素；如果链表的长度是偶数，那就可以等分。可以使用快慢指针获取到链表的中间位置。

算法刷题目链表

2023-10-11

Source

Edit

History

反转链表

一、题目

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

进阶：部分链表反转。给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

1 2	输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]

Leetcode：https://leetcode.cn/problems/reverse-linked-list-ii/

算法刷题目链表

2023-10-11

Source

Edit

History

合并两个排序链表

一、题目

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

leetcode：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

二、思路

简单，注意开始的指向和结束的指向

三、code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        ListNode* res = NULL;
        if (l1->val < l2->val) {
            res = l1;
            l1 = l1->next;
        } else {
            res = l2;
            l2 = l2->next;
        }
        ListNode* tmp = res;
        for (; l1 != NULL && l2 != NULL;) {
            if (l1->val < l2->val) {
                tmp->next = l1;
                l1 = l1->next;
            } else {
                tmp->next = l2;
                l2 = l2->next;
            }
            tmp = tmp->next;
        }
        for (; l1 != NULL;) {
            tmp->next = l1;
            tmp = tmp->next;
            l1 = l1->next;
        }
        for (; l2 != NULL;) {
            tmp->next = l2;
            tmp = tmp->next;
            l2 = l2->next;
        }
        return res;
    }
};

算法刷题目链表

2023-10-11

Source

Edit

History

打印两个有序链表的公共部分

一、题目

给定两个有序链表的头指针，打印两个链表的公共部分

输入两个链表，找出它们的第一个公共节点

Leetcode：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

二、思路

如果两个链表有公共部分，说明两个链表相交。而且这两个链表有序。那么依次遍历即可

对于找到一个公共节点的问题。使用双指针的方式。

一、题目

一个链表，特点是奇数位升序偶数位降序，使得链表变成升序的。

1
2
3

1 200 2 100 3 50 4 30 5
===>
1 2 3 4 5 30 50 100 200

二、分析

这道题目三步走：

算法刷题目链表

2023-10-11

Source

Edit

History

链表中倒数第k个节点

一、题目

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点

二、思路

单链表，两个指针，一个指针先走 K 步，然后两个指针一起走，直到先走 K 步的那个指针到达链表尾部

三、code

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

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if (head == nullptr) return nullptr;
        ListNode* fast = head, *slow = head;
        for (; fast != nullptr && k-- > 0;) {
            fast = fast->next;
        }
        for (; fast != nullptr && slow != nullptr;) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

ListNode* get_list(const std::vector<int>& vec) {
    ListNode* node = new ListNode(vec[0]);
    ListNode* tmp = node;
    for (size_t i = 1; i < vec.size(); ++i) {
        tmp->next = new ListNode(vec[i]);
        tmp = tmp->next;
    }
    return node;
}

void print_list(ListNode* node) {
    for (; node != nullptr;) {
        std::cout << node->val << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    Solution s;
    ListNode* list = get_list({1, 2, 3, 4, 5});
    print_list(list);
    ListNode* node = s.getKthFromEnd(list, 2);
    print_list(node);
    return 0;
}

算法刷题目链表

2023-10-11

Source

Edit

History

旋转链表

一、旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

Leetcode：https://leetcode.cn/problems/rotate-list/description/

二、分析

链表问题比较简单，来一个 node 指针，和一个 len 来记录链表长度，遍历一次链表求出长度。然后让 node 的 next 指向 head，将链表变成一个环形的。

根据 K，计算出还要走 len-k 步，可以到达结果链表头节点的前一个位置。注意 len-k，应该为 len-k%len，因为 K 有可能大于 len。最后返回 node 下一个节点即可

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    explicit ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr || k == 0) {
            return head;
        }
        ListNode* node = head;
        int len = 1;
        while (node->next != nullptr) {
            len++;
            node = node->next;
        }
        int add = len - k%len;
        if (add == len) {
            return head;
        }
        node->next = head;
        while (add--) {
            node = node->next;
        }
        ListNode* res = node->next;
        node->next = nullptr;
        return res;
    }
};