上接 链表相关算法题 面试必备（一）

目录

链表的中间节点两个链表的第一个公共节点合并两个有序的链表合并k个有序的链表删除排序链表在重复的元素单链表冒泡排序单链表快速排序单链表归并排序

9. 链表的中间节点 LeetCode876

给定一个单链表pHead，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

ListNode* findMiddleNode(ListNode* pHead) { if (pHead == nullptr) return pHead; ListNode* pFast = pHead; ListNode* pSlow = pHead; while (pFast->next != nullptr && pFast->next->next != nullptr) { pFast = pFast->next->next; pSlow = pSlow->next; } if(pFast->next==nullptr) return pSlow; else return pSlow->next; }

10. 两个链表的第一个公共节点 剑指offer 52

输入两个链表pHeadA和pHeadB，找出它们的第一个公共节点。

ListNode* getFirstCommonNode(ListNode *pHeadA, ListNode *pHeadB) { if(pHeadA==nullptr || pHeadB==nullptr) return nullptr; int lenA=getListLength(pHeadA); int lenB=getListLength(pHeadB); ListNode* pLong=pHeadA; ListNode* pShort=pHeadB; int len=lenA-lenB; if(len<0){ pLong=pHeadB; pShort=pHeadA; len=-len; } for(int i=0;i<len;i++) pLong=pLong->next; while(pShort!=nullptr && pShort!=pLong){ pShort=pShort->next; pLong=pLong->next; } return pShort; } int getListLength(ListNode* pHead){ if(pHead==nullptr) return 0; ListNode* pNode=pHead; int count=0; while(pNode!=nullptr){ count++; pNode=pNode->next; } return count; }

11. 合并两个有序的链表 LeetCode 21

将两个升序链表合并为一个新的升序链表，新链表是通过拼接给定的两个链表的所有节点组成的。

//迭代 ListNode* mergeTwoLists(ListNode* pHead1, ListNode* pHead2) { ListNode* pHair=new ListNode(-1); ListNode* pNode=pHair; while(pHead1!=nullptr && pHead2!=nullptr){ if(pHead1->val<pHead2->val){ pNode->next=pHead1; pHead1=pHead1->next; } else{ pNode->next=pHead2; pHead2=pHead2->next; } pNode=pNode->next; } if(pHead1==nullptr) pNode->next=pHead2; if(pHead2==nullptr) pNode->next=pHead1; return pHair->next; } //递归 ListNode* mergeTwoLists(ListNode* pHead1, ListNode* pHead2) { if(pHead1==nullptr || pHead2==nullptr) return pHead1==nullptr?pHead2:pHead1; if(pHead1->val<pHead2->val){ pHead1->next=mergeTwoLists(pHead1->next, pHead2); return pHead1; } else{ pHead2->next=mergeTwoLists(pHead1, pHead2->next); return pHead2; } }

12. 合并k个有序的链表 LeetCode 23

给定一个链表数组，每个链表都已经按升序排列，将所有链表合并到一个升序链表中。

ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size()==0) return nullptr; return mergeKLists(lists,0,lists.size()-1); } ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right) { if(left>right) return nullptr; if(left==right) return lists[left]; int mid=left+(right-left)/2; ListNode* mergeLeft=mergeKLists(lists,left,mid); ListNode* mergeRight=mergeKLists(lists,mid+1,right); return mergeTwoList(mergeLeft, mergeRight); }

13. 删除排序链表中重复的元素 LeetCode 82

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。 LeetCode 83 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

ListNode* deleteDuplicates(ListNode* pHead) { if(pHead==nullptr || pHead->next==nullptr) return pHead; ListNode* pHair=new ListNode(-1); pHair->next=pHead; ListNode* pPre=pHair; ListNode* pNode=pHead; while(pNode!=nullptr){ ListNode* pNext=pNode->next; if(pNext!=nullptr && pNext->val==pNode->val){ while(pNext->next!=nullptr && pNext->next->val==pNode->val) pNext=pNext->next; pPre->next=pNext->next; pNode=pNext->next; } else{ pPre=pNode; pNode=pNext; } } return pHair->next; }

14. 单链表冒泡排序

ListNode* bubbleSortList(ListNode* pHead) { if (pHead == nullptr || pHead->next == nullptr) return pHead; int len = getListLength(pHead); ListNode* pHair = new ListNode(-1); pHair->next = pHead; for (int i = 0; i < len - 1; i++) { ListNode* pPre = pHair; ListNode* pNode = pHair->next; ListNode* pNext = pNode->next; for (int j = 0; j < len - 1 - i; j++) { if (pNode->val > pNext->val) { pPre->next = pNext; pNode->next = pNext->next; pNext->next = pNode; } pPre = pPre->next; pNode = pPre->next; pNext = pNode->next; } } return pHair->next; } int getListLength(ListNode* pHead) { if (pHead == nullptr) return 0; return 1 + getListLength(pHead->next); }

15. 单链表快速排序

ListNode* qucikSortList(ListNode* pHead) { if (pHead == nullptr || pHead->next == nullptr) return pHead; vector<ListNode*> result = partition(pHead); ListNode* pLeft = qucikSortList(result[0]); ListNode* pRight = qucikSortList(result[2]); result[1]->next = pRight; if (pLeft == nullptr) return result[1]; else { ListNode* pNode = pLeft; while (pNode->next != nullptr) pNode = pNode->next; pNode->next = result[1]; return pLeft; } } vector<ListNode*> partition(ListNode* pHead) { ListNode* pHair1 = new ListNode(-1); ListNode* pHair2 = new ListNode(-1); ListNode* pNode1 = pHair1; ListNode* pNode2 = pHair2; int temp = pHead->val; ListNode* pNode = pHead->next; while (pNode != nullptr) { if (pNode->val < temp) { pNode1->next = pNode; pNode1 = pNode1->next; } else { pNode2->next = pNode; pNode2 = pNode2->next; } pNode = pNode->next; } pNode1->next = nullptr; pHead->next = nullptr; pNode2->next = nullptr; return { pHair1->next,pHead,pHair2->next }; }

16. 单链表归并排序

ListNode* mergeSortList(ListNode* pHead) { if (pHead == nullptr || pHead->next == nullptr) return pHead; ListNode* pSlow = pHead; ListNode* pFast = pHead; while (pFast->next != nullptr && pFast->next->next != nullptr) { pFast = pFast->next->next; pSlow = pSlow->next; } ListNode* pHead2 = pSlow->next; pSlow->next = nullptr; ListNode* pLeft = mergeSortList(pHead); ListNode* pRight = mergeSortList(pHead2); return mergeTwoList(pLeft, pRight); } ListNode* mergeTwoLists(ListNode* pHead1, ListNode* pHead2) { if(pHead1==nullptr || pHead2==nullptr) return pHead1==nullptr?pHead2:pHead1; if(pHead1->val<pHead2->val){ pHead1->next=mergeTwoLists(pHead1->next, pHead2); return pHead1; } else{ pHead2->next=mergeTwoLists(pHead1, pHead2->next); return pHead2; } }