【剑指Offer】 总结
链表类题目：
剑指Offer题6: 从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路1： 使用栈的先入后出的思想，先遍历一遍并存入栈，后面再弹出保存即可
vector<int> printListFromTailToHead(ListNode* head) {
// 定义一个栈
stack<int> nodes;
// 遍历入栈每个节点的值
ListNode* pNode = head;
while (pNode) {
nodes.push(pNode->val);
pNode = pNode->next;
}
// 将其放入结果中
vector<int> res;
while (!nodes.empty()) {
res.push_back(nodes.top());
nodes.pop();
}
return res;
}思路2: 使用递归的思路，先达到最深，然后再一步一步操作（取出值），则达到反序的效果。
vector<int> res;
vector<int> printListFromTailToHead(ListNode* head) {
if(head) {
// 先往深处递归
if(head->next!=NULL){
printListFromTailToHead(head->next);
}
// 再操作（此处为将值取出）
res.push_back(head->val);
}
return res;
}
剑指Offer题18: 删除链表的节点
1，删除链表的某个指定节点p
将该节点后一个节点的值复制，再跳过后一个节点即可。
伪代码：
if p->next 不为空:
pNext = p->next;
p->val = pNext->val;
p->next = pNext->next;
delete pNext;
pNext = nullptr;
else if p == pHead : // p不是尾节点且等于头节点，说明只有一个节点。
delete p;
p = nullptr;
head = nullptr;
else: // 是尾节点且不是头节点时，则循环至前一位，再将next置空即可
q = pHead;
while (q->next != p) // 循环直至p的前一处
q = q->next;
q->next = nullptr;
delete p;
p = nullptr;这个做法需要假定需删除的节点p必定存在与head链表中。
2， 删除链表中的重复节点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
使用递归的方法，
ListNode* deleteDuplication(ListNode* pHead) {
// 若链表为空或者只有头节点
if (pHead == nullptr || pHead->next == nullptr)
return pHead;
// 若当前节点的值与下一个的值一样，即为重复时，取pNode为后指针，往后挪，直至不再重复
// 如 2 2 2 4 5 ， pHead为2， pNode至4时跳出循环，再处理后面的部分
if (pHead->val == pHead->next->val) {
ListNode* pNode = pHead->next;
while (pNode != nullptr && pNode->val == pHead->val)
pNode = pNode->next;
return deleteDuplication(pNode);
}
// 当前值与下一处不相同时，则连入该点的->next为下一点的递归结果
else {
pHead->next = deleteDuplication(pHead->next);
return pHead;
}
}
剑指Offer题22: 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个结点。
使用两个指针，首先让pAhead先走k-1步，再让两个指针同时走，直至pAhead到链表尾。此时另一个节点即为求的节点。
用到的next的节点都要注意是否为空。1，判断头节点是否为空；2，在pAhead先行时，随时检测是否超出，即k大于了链表长度。
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == nullptr || k==0) // 若k为int则判断k<=0
return nullptr;
ListNode* pBehind = pListHead;
ListNode* pAhead = pListHead;
// 让pAhead先走k-1个。
for (unsigned int i=0; i<k-1; i++) {
pAhead = pAhead->next;
// 若走到下一步为空
if (pAhead == nullptr)
return nullptr;
}
// 两个指针一起走，直至pAhead走到尾，pBehind即为结果
while(pAhead->next != nullptr) {
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}剑指Offer题23: 链表中环的入口节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
首先确认有环。两个指针一快一慢，一直循环至两者相遇于节点p ==> 有环，或快的节点->next为空 ==> 无环。
确认有环的情况下，如何找入口节点。两种方法：
方法1， 相遇节点p必处于环内，首先循环一遍至回到原位，得到环内共有n个节点，再在链表表头用两个指针，一个先走n步，然后再一起走，相遇节点即为环的入口节点。
方法2， 两个指针，一个在头节点，另一个在相遇节点p，同时移动，相遇点即为环入口节点，证明见下：
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
// 先确认是否有环，若有环则pAhead/pBehind为重合结点，无环则返回nullptr
if (pHead == nullptr || pHead->next == nullptr || pHead->next->next == nullptr)
return nullptr;
ListNode* pBehind = pHead->next;
ListNode* pAhead = pBehind->next;
while (pBehind != pAhead) {
if (pAhead == nullptr || pAhead->next == nullptr || pAhead->next->next == nullptr)
return nullptr; // 走出链表，说明无环
pBehind = pBehind->next;
pAhead = pAhead->next->next;
}
/*
// 方法一：拿到重合处的节点，即环内的节点，做一次循环得到环的长度
ListNode* pNode = pAhead->next;
int loop_len = 1;
while (pNode != pAhead) {
pNode = pNode->next;
loop_len++;
}
// 得到环的长度后，使用两个指针，一个先走loop_len步，之后重合处即是环入口
pAhead = pHead;
pBehind = pHead;
for (int i=0; i<loop_len; i++)
pAhead = pAhead->next;
while (pAhead != pBehind) {
pAhead = pAhead->next;
pBehind = pBehind->next;
} */
// 方法二，将一个指针重置到头节点处，另一个从相遇处，同时出发，相遇处即为环入口
pBehind = pHead;
while (pBehind != pAhead) {
pBehind = pBehind->next;
pAhead = pAhead->next;
}
return pAhead;
}剑指Offer题24: 反转链表
输入一个链表，反转链表后，输出新链表的表头。
思路，使用一个指针p2从头节点往后遍历直至为空，每一步时，先使用一个指针p3来记录p2的next，再将p2的next指向上一个节点p1，然后将p2更新至下一节点，同时上一节点p1也更新。
ListNode* ReverseList(ListNode* pHead) {
if (pHead == nullptr || pHead->next == nullptr)
return pHead;
ListNode* p1 = nullptr;
ListNode* p2 = pHead;
ListNode* p3;
while (p2 != nullptr) {
p3 = p2->next; // 记录p2的next
p2->next = p1; // p2翻转
p1 = p2; // 更新
p2 = p3; // 更新
}
return p1; // 最后循环结束时p2为空，故返回的是p1
}剑指Offer题25: 合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
每次都等于是找到一个当前两个链表的头节点的最大的节点，可用递归解决。
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == nullptr)
return pHead2;
if (pHead2 == nullptr)
return pHead1;
ListNode* pMergeHead = nullptr;
if (pHead1->val < pHead2->val) {
pMergeHead = pHead1;
pMergeHead->next = Merge(pHead1->next, pHead2);
}
else {
pMergeHead = pHead2;
pMergeHead->next = Merge(pHead1, pHead2->next);
}
return pMergeHead;
}剑指Offer题52: 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共结点。
先求的两个链表的长度差，然后让长的链表先走，之后在一起走，相同时则为第一个公共节点。
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
// 先得到两个链表的长度
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
int len1 = 0;
int len2 = 0;
while(p1 != nullptr) {
p1 = p1->next;
len1++;
}
while(p2 != nullptr) {
p2 = p2->next;
len2++;
}
// 再确定下来长链表和短链表，以及长度差
ListNode* pLong = pHead1;
ListNode* pShort = pHead2;
int lenDif = len1-len2;
if (len2 > len1) {
pLong = pHead2;
pShort = pHead1;
lenDif = len2-len1;
}
// 长链表先行长度差个节点
for (int i=0; i<lenDif; i++)
pLong = pLong->next;
// 两个一起走，直至到达公共节点（也可能不存在公共节点，则会走到nullptr处，最后返回的也会是nullptr）
while (pLong != pShort) {
pLong = pLong->next;
pShort = pShort->next;
}
return pLong;
}