【剑指offer】链表 系列
🌈前言🌈
因为版权问题，leetcode下架了剑指offer系列题目，但是换汤不换药，命名LCR开头的题目依然是剑指offer系列题目的解题思路。
秉持开源思想，我在牛客买下【剑指offer】后，将各个题目的描述以及解题思路记录了下来，方便大家免费的来刷这些题目，解决了在leetcode需要查找对应的题目的麻烦，以避免大家需要在牛客上买实体书才能刷题的困境。
📁 从尾到头打印链表
很简单的一道递归题目，递归到最底层，然后从后往前记录就可以了。
class Solution {
public:vector<int> ans;vector<int> printListFromTailToHead(ListNode* head) {if(head == nullptr)return ans;printListFromTailToHead(head->next);ans.push_back(head->val);return ans; }
};📁 反转链表
采用递归的思路，递归到最后一个节点时，保存该节点为新的新的头结点，然后从后往前修改指向即可。
class Solution {
public:ListNode* ReverseList(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;ListNode* newHead = ReverseList(head->next);head->next->next = head;head->next = nullptr;return newHead;}
};📁 合并两个排序的链表
新创建一个链表，每次将两个链表中较小的节点链入新链表中，遍历两个链表。
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {// write code hereListNode* newHead = new ListNode(-1);ListNode* tail = newHead;while(pHead1 && pHead2){if(pHead1->val < pHead2->val){tail->next = pHead1;tail = tail->next;pHead1 = pHead1->next;}else {tail->next = pHead2;tail = tail->next;pHead2 = pHead2->next;}}//到此，一定有一个链表遍历完成，将还有节点的链表直接链入新链表即可if(pHead1)tail->next = pHead1;if(pHead2)tail->next = pHead2;//良好的代码风格，申请需释放 当然笔试不比这么严谨tail = newHead->next;delete newHead;return newHead->next;}
};📁 两个链表的第一个公共结点
让两个指针分别遍历两个链表，遍历完一个链表后在遍历另一个链表，这样两个节点走的路程是一样的，如果存在公共节点，他们一定会在第一个公共节点相遇，如果不存在会都等于null。
即当两个指针都遍历完各自的链表后，当最后一个遍历完成指针位于另一个链表后，他们剩余的路程是一样的，如果存在公共节点，他们一定会在第一个公共节点相遇，如果不存在会都等于null。。
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {ListNode* p1 = pHead1, *p2 = pHead2;while(p1 != p2){p1 = p1 == nullptr ? pHead2 : p1->next;p2 = p2 == nullptr ? pHead1 : p2->next;}return p1;}
};📁 JZ23 链表中环的入口结点
做题目之前，需要了解一下 142. 环形链表 II，知道什么什么是相遇点。本题就是在此基础上做出来的。
采用双指针，一个指针从从头开始，另一个指针从相遇点开始，他们相遇点就是环形链表的入口节点。
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* fast= pHead , *slow = pHead;while(fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow){ListNode* cur = pHead;while(cur != slow){cur = cur->next;slow = slow->next; }return cur;}}return nullptr;}
};📁 链表中倒数最后k个结点
class Solution {
public:ListNode* FindKthToTail(ListNode* pHead, int k) {int n = 0;ListNode* cur = pHead;while(cur){cur = cur->next;++n;}n -= k;if(n < 0)return nullptr;cur = pHead;while(n--){cur = cur->next;}return cur;}
};📁 JZ35 复杂链表的复制
采用哈希记录创建下来的新节点，这样当我们创建一个节点后，随机指针从哈希中获取。如果哈希中没有就创建，有就返回。
class Solution {
public:unordered_map<RandomListNode* , RandomListNode*> hash;RandomListNode* Clone(RandomListNode* pHead) {if(pHead == nullptr)return nullptr;if(hash.find(pHead) == hash.end()){ RandomListNode* node = new RandomListNode(pHead->label);hash[pHead] = node;node->next = Clone(pHead->next);node->random = Clone(pHead->random);}return hash[pHead];}
};📁 删除链表中重复的结点
我们创建一个新列表，里面只能将没有重复值的节点链入。首先我们先对每个节点的值进行统计遍历，第二次再将没有重复值的节点链入。
class Solution {
public:ListNode* deleteDuplication(ListNode* head) {ListNode* newHead = new ListNode(-1);ListNode* tail = newHead;ListNode* cur = head;unordered_map<int,int> hash;while(cur)hash[cur->val]++ , cur = cur->next;cur = head;while(cur){if(hash[cur->val] == 1){tail->next = cur; tail = tail->next;}cur = cur->next;}//特殊情况处理，最后一个没有重复节点后面还有重复节点，直接置为空即可tail->next = nullptr;return newHead->next;}
};📁 删除链表的节点
采用递归的方法。返回值是不包含val值节点的链表的头结点。如果当前节点val == val，直接返回next即可。
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {if(head == nullptr || head->next == nullptr)return head;if(head->val == val)return head->next;head->next = deleteNode(head->next, val);return head;}
};