06.从尾到头打印链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public:vector<int> reversePrint(ListNode* head) {vector<int> ret;function<void(ListNode*)>dfs = [&](ListNode* head){if(!head){return;}dfs(head->next);ret.push_back(head->val);return;};dfs(head);return ret;}};
24.反转链表
递归
递归的想法就在于假设链表的其余部分已经被反转，现在应该如何反转它前面的部分。
推广来说，递归就是选一个完成到中间的情况来看下一步应该怎么做。
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;
}
};
迭代
迭代写法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL, *cur = head, *next;
while(cur){
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
复杂链表的复制（重点）
这一题有细节的，关键就在这个哈希表的设计，设计的目的就是避免重复拷贝的情况发生。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> cachedNode;
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
if (!cachedNode.count(head)) {
Node* headNew = new Node(head->val);
cachedNode[head] = headNew;
headNew->next = copyRandomList(head->next);
headNew->random = copyRandomList(head->random);
}
return cachedNode[head];
}
};
快慢指针
剑指 Offer II 021. 删除链表的倒数第 n 个结点
- 这题写过，先使用一个快指针来指向n所在的位置，然后使用一个慢指针从头开始
- 然后快慢指针同时开始，当快指针指向空时，满指针所在的位置就是倒数第n个节点
注意如果在赋值之前调用属于链表的功能，就需要使用 new来初始化！！！
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *quick = head,*dummy = new ListNode(),*pre; dummy->next = head; pre = dummy; while(n){ n--; quick = quick->next; } while(quick){ quick = quick->next; pre = head; head = head->next; } pre->next= head->next; return dummy->next; } };剑指 Offer II 022. 链表中环的入口节点
先使用快慢指针同时从head开始跑，当相遇时就代表有环
- 然后head指针和slow同时同速度开始跑，当相遇时，这个节点即为入口节点
这是由数学方法得到的
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode*slow = head, *fast = head; do{ if(!fast||!fast->next) return NULL; fast = fast->next->next; slow = slow->next; } while (fast != slow); fast = head; while(fast != slow){ slow = slow->next; fast = fast->next; } return fast; } };剑指 Offer II 023. 两个链表的第一个重合节点
两个指针同时从头开始跑，当到达null之后就从对方的头开始，当相等的时候就代表是第一个重合节点，如果相等且为空就代表没有重合部分
这里可以使用数学来证明！！！
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode*node1 = headA, *node2 = headB; while(node1!=node2){ if(!node1) node1 = headB; else node1 = node1->next; if(!node2) node2 = headA; else node2 = node2->next; } return node1; } };链表的数学操作
剑指 Offer II 025. 链表中的两数相加
反转链表写法
我的写法，比较笨，先反转两条，然后相加，然后反转回来
显然使用迭代来做更加简单！！！class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { l1 = reverseList(l1); l2 = reverseList(l2); int bite = 0; return reverseList(dfs(l1, l2, bite)); } ListNode* dfs(ListNode* l1, ListNode* l2, int bite){ if(!l1||!l2){ if(bite == 0) return l1? l1:l2; else { l1 = l1? l1:l2; if(!l1){ ListNode* node = new ListNode(1); node->next = nullptr; return node; } else { ListNode* l3 = l1; while(bite){ int sum = l3->val+bite; bite = sum/10; l3->val = sum%10; if(!bite) break; if(!l3->next) { ListNode* node = new ListNode(1); l3->next = node; node->next = nullptr; break; } l3 = l3->next; } return l1; } } } int sum = l2->val + l1->val + bite; bite = sum/10; ListNode* node = new ListNode(sum%10); node->next = dfs(l1->next, l2->next, bite); return node; } ListNode* reverseList(ListNode* head) { if(!head||!head->next) { return head; } ListNode* newhead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newhead; } };简单写法
这里的加法部分使用迭代比较简单
注意使用一个哑节点，dummy来指向前一个节点class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { //若任一链表为空，则直接返回另一链表 if (l1 == nullptr || l2 == nullptr) return l1 == nullptr ? l2 : l1; l1 = reverseList(l1), l2 = reverseList(l2); //反转链表，便于进行加法运算 return reverseList(addList(l1, l2)); //相加后再反转，最后返回结果 } ListNode* reverseList(ListNode* head) //反转链表模板 { if (head == nullptr) return head; ListNode *pre = head, *cur = head->next; while (cur) { ListNode *ne = cur->next; cur->next = pre; pre = cur, cur = ne; } head->next = nullptr; return pre; } ListNode* addList(ListNode* l1, ListNode* l2) //链表相加 { ListNode *dummy = new ListNode(0), *p = dummy; int carry = 0; //进位标志 while (l1 || l2) { //链表不为空就将当前的两个节点的值加起来，为空就加0 carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val); //如果当前节点有进位，就取模后为1，没有进位就保持原值 //p = p->next = xx 表示 p->next = xx, p = p->next两条语句的组合 p = p->next = new ListNode(carry % 10); //如果有进位，则carry余1， 没有进位则carry重置为0 carry /= 10; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } //判断最高位是否有进位，有的话就再追加一个1即可 if (carry) p->next = new ListNode(1); return dummy->next; } };使用栈来做
这里主要是因为加法操作是从低位到高位，链表的元素需要反着来遍历，利用栈的先进后出的特性也能满足条件
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int> num1,num2; //使用栈来存储元素 while(l1 != nullptr){ num1.push(l1->val); l1 = l1->next; } while(l2 != nullptr){ num2.push(l2->val); l2 = l2->next; } int jw = 0;//进位符号 ListNode* p = nullptr;//直接反着构造，这里的p就是最后一个节点的next while(!num1.empty() || !num2.empty() || jw){ int n1 =num1.empty() ? 0 : num1.top(); int n2 = num2.empty() ? 0 :num2.top(); if(!num1.empty()) num1.pop(); if(!num2.empty()) num2.pop(); int num = n1 + n2 + jw; jw = num / 10; num = num % 10; ListNode* newnode = new ListNode(num,p);//直接反着构造！！ p = newnode; } return p;//因为是直接反着构造的，所以最终的p就是头节点 } };剑指 Offer II 026. 重排链表
线性链表
使用一个vector来储存链表的节点，因为链表不支持下标访问，所以利用线性表的下标来直接按照顺序访问指定元素
class Solution { public: void reorderList(ListNode *head) { if (head == nullptr) { return; } vector<ListNode *> vec; ListNode *node = head; while (node != nullptr) { vec.emplace_back(node); node = node->next; } int i = 0, j = vec.size() - 1; while (i < j) { vec[i]->next = vec[j]; i++; if (i == j) { break; } vec[j]->next = vec[i]; j--; } vec[i]->next = nullptr; } };寻找链表中点+链表逆序+合并链表
通过快慢指针找到链表的中点
- 将链表的右半端翻转
将链表的左半端和右半端和并
class Solution { public: void reorderList(ListNode* head) { if (head == nullptr) { return; } ListNode* mid = middleNode(head); ListNode* l1 = head; ListNode* l2 = mid->next;//注意mid为第一个链表的结尾 mid->next = nullptr; l2 = reverseList(l2); mergeList(l1, l2); } ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; } ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr != nullptr) { ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; } void mergeList(ListNode* l1, ListNode* l2) { ListNode* l1_tmp; ListNode* l2_tmp; while (l1 != nullptr && l2 != nullptr) { l1_tmp = l1->next; l2_tmp = l2->next; l1->next = l2; l1 = l1_tmp; l2->next = l1; l2 = l2_tmp; } } };剑指 Offer II 027. 回文链表（同上）
与上一题类似
-
双向链表
剑指 Offer II 028. 展平多级双向链表（深度优先搜索）
出现了几个问题，其他的都比较简单
返回的head已经改变了没有注意到
没有考虑到空指针的情况。
/* // Definition for a Node. class Node { public: int val; Node* prev; Node* next; Node* child; }; */ class Solution { public: Node* flatten(Node* head) { if(!head) return NULL; Node* newhead = head; if(head->child) { Node* next = head->next; head->child->prev = head; head->next = flatten(head->child); head->child = NULL; while(head->next){ head = head->next; } head->next = next; if(next) next->prev = head;//这里注意考虑到空指针的情况 } flatten(head->next); return newhead;//这里注意不要改变输入进来的head，因此先使用一个newhead来保存 } };循环链表
剑指 Offer II 029. 排序的循环链表（重点）
注释已经写的很清楚了
- 三种情况
- 一个节点的情况不用考虑，因为是循环链表
class Solution { public: /* 3种插入情况： 1) cur.val <= x <= cur.next.val 顺序插入 2) 插入点为为序列的边界跳跃点： 如 3->4->1 插入5，这样 1(cur->next)<4(cur)<5(x) 4为插入点的前驱节点；这种情况表示x比最大值都大 如 3->4->1 插入0，这样 0(x)<1(cur->next)<4(cur) 4为插入点的前驱节点；这种情况表示x比最小值都小 */ Node* insert(Node* head, int x) { if(!head){ head=new Node(x); head->next=head; return head; } Node *cur=head; while(cur->next!=head){ // cur 为边界跳越点 if(cur->next->val<cur->val){//找边界点比较好 if(x>=cur->val)break;// x比最大值都大 if(x<=cur->next->val)break;// x比最小值都小 } // 顺序插入x中升序序列中 if(x>=cur->val&&x<=cur->next->val)break; cur=cur->next; } // 将x插入到cur与cur->next之间 cur->next=new Node(x,cur->next); return head; } };
若有收获，就点个赞吧
0 人点赞
