数据结构刷题：第八天

目录

一，反转链表

1，迭代

复杂度分析

2，递归

复杂度分析

二，删除排序链表中的重复元素

1，一次遍历

思路与算法

代码

复杂度分析

一，反转链表

206. 反转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list/?envType=study-plan&id=shu-ju-jie-gou-ru-men

1，迭代

假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。

在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

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

复杂度分析

• 时间复杂度：O(n)，其中 nn 是链表的长度。需要遍历链表一次。

• 空间复杂度：O(1)。

2，递归

递归版本稍微复杂-些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何
反转它前面的部分?
假设链表为:
n1-→...→+nk-1→nk→nk+1→...→nm→0

若从节点nk+1到nm已经被反转，而我们正处于nk
n1→...→nk-1→Nh:→nk+1←...←nm
我们希望nk+1的下一个节点指向nk所以，np.next.next= nk。
需要注意的是n1的下一个节点必须指向0。如果忽略了这一点,链表中可能会产生环。
 

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

复杂度分析

时间复杂度：O(n)，其中n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

二，删除排序链表中的重复元素

83. 删除排序链表中的重复元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-duplicates-from-sorted-list/?envType=study-plan&id=shu-ju-jie-gou-ru-men

1，一次遍历

思路与算法

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

具体地，我们从指针cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与 cur.next 对应的元素相同，那么我们就将 cur.next 从链表中移除；否则说明链表中已经不存在其它与 cur 对应的元素相同的节点，因此可以将cur 指向 cur.next。

当遍历完整个链表之后，我们返回链表的头节点即可。

细节

当我们遍历到链表的最后一个节点时，cur.next 为空节点，如果不加以判断，访问 cur.next 对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点，而不需要遍历完整个链表。

代码

注意下面C++ 代码中并没有释放被删除的链表节点的空间。如果在面试中遇到本题，读者需要针对这一细节与面试官进行沟通。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }
 
        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }
 
        return head;
    }
};

复杂度分析

• 时间复杂度：O(n)，其中 nn 是链表的长度。

• 空间复杂度：O(1)。