[模板总结] - 单向链表LinkedList操作

题目汇总

Leetcode 21, 82, 160, 206, 237, 268

Leetcode 21. 合并两个有序链表

归并排序的思路，创建一个哨兵节点从两个链表中按大小插入即可。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dum = new ListNode(-1);ListNode* curr = dum;while(list1 && list2) {if (list1->val < list2->val) {curr->next = list1;list1 = list1->next;} else {curr->next = list2;list2 = list2->next;}curr = curr->next;}while(list1) {curr->next = list1;curr = curr->next;list1 = list1->next;}while(list2) {curr->next = list2;curr = curr->next;list2 = list2->next;}return dum->next;}
};

时间复杂度：$\mathcal{O}(N+M)$
空间复杂度：$\mathcal{O}(1)$

Leetcode.82 Linkedlist中删除所有重复片段

这道题目要求是删除所有重复的片段，而不仅仅是去重，基本思路就是线性扫描，如果扫描的片段有重复也就是长度大于1那么就跳过这部分，接着找下面，如果查看部分长度==1那么就将该元素加入结果。在循环时维持一个循环不变量

建立一个pred节点，这个节点在每一个循环开始时一定指向的是当前最新的不重复节点位置

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* dum = new ListNode(-1);dum->next = head;auto pred = dum; // 哨兵节点作为第一个不会重复的节点while(pred->next) {/*循环不变量 ->pred前驱节点时刻定位*/auto p1 = pred->next;while(p1 && pred->next->val==p1->val) {p1 = p1->next;}//确定是不是要更新pred到新的不重复if (pred->next->next==p1) pred = pred->next; //遇到新的不重复节点，更新pred的位置else pred->next = p1; // 跳过当前重复片段，pred指向下一个片段开始位置，但这里不更新pred位置因为当前p1位置可能重复，需要下一个循环进行检测.}return dum->next;}
};

时间复杂度：$\mathcal{O}(N)$
空间复杂度：$\mathcal{O}(1)$

Leetcode 206. 反转一个单向链表

要求in-place反转，基本思路可以进行递归反转，在每一次递归中把下一层返回节点的next指向当前节点即可。
第二种方法是利用迭代的方式，每一次循环中，保存当前节点的下一个节点nxt，并把当前节点next连接前一个节点prev，然后更新prev为当前节点，然后继续遍历。

//递归解法
class Solution {
public:ListNode* ans = new ListNode(-1);ListNode* reverseList(ListNode* head) {dfs(head);return ans->next;}ListNode* dfs(ListNode* head) {if(!head || !head->next) {//保存反转头节点ans->next = head;return head;} ListNode* res = dfs(head->next);//反转当前节点res->next = head;//断开当前节点与next节点连接res->next->next = nullptr;//返回当前节点return res->next;}
};//迭代解法
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;while(head) {ListNode* curr = head;head = head->next;curr->next = prev;prev = curr;}return prev;}
};

时间复杂度：递归、迭代都是 $\mathcal{O}(N)$
空间复杂度：递归： $\mathcal{O}(N)$ 栈的深度。迭代：$\mathcal{O}(1)$