目录

向单链表尾部插入元素删除单链表中第一个值为x的节点删除单链表中的目标节点从尾到头打印单链表单链表中倒数第k个节点反转单链表k个一组反转翻单链表链表是否有环以及环的入口

定义单链表

struct ListNode { int val; ListNode* next; ListNode(int value) :val(value), next(nullptr) {} };

1. 向单链表尾部插入元素

ListNode* insertTail(ListNode* pHead, int x) { if (pHead == nullptr) return new ListNode(x); ListNode* pNode = pHead; while (pNode->next != nullptr) pNode = pNode->next; pNode->next = new ListNode(x); return pHead; }

2. 删除单链表中第一个值为x的节点 剑指offer 18

ListNode* deleteFirstTarget(ListNode* pHead, int x) { if (pHead == nullptr) return pHead; if (pHead->val == x) return pHead->next; ListNode* pPre = pHead; ListNode* pNode = pHead->next; while (pNode != nullptr && pNode->val != x) { pPre = pNode; pNode = pNode->next; } if (pNode != nullptr) pPre->next = pNode->next; return pHead; }

3. 删除单链表中的目标节点

void deleteTargetNode(ListNode** pHead, ListNode* pTarget) { if (pHead==nullptr || *pHead == nullptr) return; if (pTarget->next != nullptr) { ListNode* pNext = pTarget->next; pTarget->val = pNext->val; pTarget->next = pNext->next; delete pNext; pNext = nullptr; } else if (pTarget == *pHead) { delete pTarget; pTarget = nullptr; *pHead = nullptr; } else { ListNode* pPre = *pHead; ListNode* pNode = (*pHead)->next; while (pNode != nullptr && pNode != pTarget) { pPre = pNode; pNode = pNode->next; } if (pNode != nullptr) { pPre->next = pNode->next; delete pTarget; pTarget = nullptr; } } }

4. 从尾到头打印单链表 剑指offer 06

//栈 vector<int> printListFromTailToFront(ListNode* pHead) { if (pHead == nullptr) return {}; vector<int> vec; stack<ListNode*> nodes; ListNode* pNode = pHead; while (pNode != nullptr) { nodes.push(pNode); pNode = pNode->next; } while (!nodes.empty()) { pNode = nodes.top(); nodes.pop(); vec.push_back(pNode->val); } return vec; } //递归 void printListFromTailToFront(ListNode* pHead, vector<int> &vec) { if (pHead == nullptr) return; printListFromTailToFront(pHead->next, vec); vec.push_back(pHead->val); } vector<int> printListFromTailToFront(ListNode* pHead) { vector<int> vec; printListFromTailToFront(pHead, vec); return vec; }

5. 单链表中倒数第k个节点 剑指offer 22

ListNode* findKthNodeFromTail(ListNode* pHead, int k) { if (pHead == nullptr || k <= 0) return nullptr; ListNode* pSlow = pHead; ListNode* pFast = pHead; for (int i = 0; i < k - 1; i++) { if (pFast->next == nullptr) return nullptr; pFast = pFast->next; } while (pFast->next != nullptr) { pFast = pFast->next; pSlow = pSlow->next; } return pSlow; }

6. 反转单链表 LeetCode 206

//迭代 ListNode* reverseList(ListNode* pHead) { ListNode* pPre = nullptr; ListNode* pNode = pHead; while (pNode != nullptr) { ListNode* pNext = pNode->next; pNode->next = pPre; pPre = pNode; pNode = pNext; } return pPre; } //递归 ListNode* reverseList(ListNode* pHead) { if(pHead==nullptr || pHead->next==nullptr) return pHead; ListNode* pNext=pHead->next; ListNode* pNewHead=reverseList(pNext); pNext->next=pHead; pHead->next=nullptr; return pNewHead; }

7. k个一组反转翻单链表 LeetCode 25

ListNode* reverseKGroup(ListNode* pHead, int k) { if (pHead==nullptr || k <= 1) return pHead; ListNode* pHair = new ListNode(-1); pHair->next = pHead; ListNode* pPre = pHair; ListNode* pLeft = pHead; while (pLeft != nullptr) { ListNode* pRight = pPre; for (int i = 0; i < k; i++) { if (pRight->next == nullptr) return pHair->next; else pRight = pRight->next; } ListNode* pNext = pRight->next; pair<ListNode*, ListNode*> result = reverseList(pLeft, pRight); pPre->next = result.first; result.second->next = pNext; pPre = result.second; pLeft = pNext; } return pHair->next; } pair<ListNode*, ListNode*> reverseList(ListNode* pLeft, ListNode* pRight) { ListNode* pPre = nullptr; ListNode* pNode = pLeft; while (pPre != pRight) { ListNode* pNext = pNode->next; pNode->next = pPre; pPre = pNode; pNode = pNext; } return { pRight,pLeft }; }

8. 链表是否有环以及环的入口 LeetCode 241 LeetCode 142

//判断是否有环 bool hasCycle(ListNode *pHead) { if(pHead==nullptr) return false; ListNode* pFast=pHead; ListNode* pSlow=pHead; while(pFast->next!=nullptr && pFast->next->next!=nullptr){ pFast=pFast->next->next; pSlow=pSlow->next; if(pFast==pSlow) return true; } return false; } //查找环的入口 ListNode *detectCycle(ListNode *pHead) { if(pHead==nullptr) return nullptr; ListNode* pSlow=pHead; ListNode* pFast=pHead; while(pFast->next!=nullptr && pFast->next->next!=nullptr){ pFast=pFast->next->next; pSlow=pSlow->next; if(pFast==pSlow){ pSlow=pHead; while(pSlow!=pFast){ pFast=pFast->next; pSlow=pSlow->next; } return pFast; } } return nullptr; }

剩余部分见 链表相关算法题 面试必备（二）