一，反转链表
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）
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)。
