趣说数据结构（练习1） —— 顺序表/链表力扣刷题

练习 1 —— 顺序表/链表力扣刷题

1. 合并两个有序链表

力扣题目地址：https://leetcode.cn/problems/merge-two-sorted-lists/

问题描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
在这里插入图片描述

解题思路：

给定的是一个有序列表，因此不需要重新排序；
典型的双指针问题，不过此处的双指针分别指两个链表的对应的指针；

解题方法一：

此份代码是通过创建一个新的链表分别存储两个链表组合后的结果。这个方法比较简单，简单来说就是两个步骤，第一步逐个比较，你们俩谁小，谁小就移动谁的指针；第二步收尾，还有谁有剩余的存库，快快交出来。

这份代码是比较 low 的，因为它需要额外开销空间，并且代码看起来多少有点不够美观。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* result = new ListNode(-1);
        ListNode* point = result;
        while(list1 != nullptr && list2 != nullptr) {
            if(list1->val <= list2->val) {
                point->next = list1;
                list1 = list1->next;
            } else {
                point->next = list2;
                list2 = list2->next;
            }
            point = point->next;
        }
        if (list1 != nullptr) {
            point->next = list1;
        }
        if (list2 != nullptr) {
            point->next = list2;
        } 
        return result->next;
    }
};

解题方法二：

以下代码来自官方文档
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

比较的简洁美观，看起来也比较舒服，除了 l1 和 l2 这种不太科学的变量命名，读起来还是非常的简单。

排除二者存在空的情况；
递归解决问题，每次递归只解决一个问题；
每次递归返回的数据都是已经完成 “部分合并” 后的结果。

坏处：此份代码使用递归需要申请额外的栈存储空间。

2. 删除排序链表中的重复元素

力扣原题地址：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

题目描述：给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

题目的示例：
在这里插入图片描述

输入：head = [1,1,2]
输出：[1,2]

问题分析：抓住关键字：已经排序的链表。

接下来的时间就简单了，我们用一个指针p，不要轻易移动，只有遇到 “与自己不一样” 的小伙伴才移动，自己才能变成它，最终就绕开了重复的元素，实现了去重的目的。

解题方法一：


class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode* now = head;
        while (now -> next) {
        	// 如果遇到的和自己相等，就绕开它到它的next
            if (now -> val == now -> next->val) {
                now -> next = now -> next->next;
            } else {
                // 不一样就保留它，加到自己的队伍
                now = now -> next;
            }
        }

        return head;
    }
};

这个解题方法比较简单，也未申请额外的存储空间，所以时间复杂度为 $O (n)$ ，而空间复杂度为 $O (1)$ 。

3. 反转链表

题目描述

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

示例

在这里插入图片描述

代码实现 1

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* result = new ListNode();
        ListNode* p = result;
        while (head != nullptr) {
            ListNode* q = new ListNode(head -> val);
            q -> next = p -> next;
            p -> next = q;
            head = head -> next;
        }

        return result -> next;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

时间复杂度已经无法降低，空间复杂度应当有改善空间，如下所示：

代码实现 2

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* next = curr -> next;
            curr -> next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

这个地方有疑问的小伙伴可以尝试先返回 curr，输出的结果是 [ ]，也就是说，之所以能够节省空间，只是我们使用两个指针移来移去的，这里我们绘制一个简单图片描述一下。

在这里插入图片描述
第一步，next = curr -> next 记录一下当前结点的下个结点的位置；
第二步，curr -> next = prev 当前结点指向的下一个结点等于 prev，请看图片中的下面一行图片，也就是说这个时候 prev 准备挪到 2 那个位置了，我们先把 curr -> next = prev，然后 prev = curr，这个时候对应的 prev 已经指向了 2 的位置；
第三步，curr = next，把 curr 拉回正轨。因为刚刚出去协助 prev 指针了，所以这里把它拉回来。