struct ListNode { int value; ListNode * next; ListNode(int v): value(v),next(NULL){} }
1链表合并
合并两个递增排序的链表
ListNode * Merge(ListNode * pHead1,ListNode * pHead2) { if(pHead1==NULL) return pHead2; else if(pHead2==NULL) return pHead1; ListNode * pMerge = NULL; if(pHead1->value < pHead2->value) { pMerge = pHead1; pMerge->next = Merge(pHead1->next,pHead2); }else { pMerge = pHead2; pMerge->next = Merge(pHead1,pHead2->next); } return pMerge; }
2 链表相加
给定两个链表，分别表示两个非负整数。它们的数字逆序存储在链表中，每个结点只存储一个数字，计算两个数字的和，并返回链表头指针
/*不带头结点*/ ListNode * Add(ListNode * head1,ListNode * head2) { ListNode* pSum = NULL; ListNode * pTail = NULL; ListNode * pCur = NULL; int carry = 0; int value = 0; while(head1 && head2) { value = carry + head1->value + head2->value; carry = value / 10; value %= 10; pCur = new ListNode(value); if(pTail) { pTail->next = pCur; pTail = pCur; }else { pSum = pCur; pTail = pCur; } head1 = head1->next; head2 = head2->next; } ListNode * p = head1 ? head1 : head2; while(p) { value = p->value +carry; carry = value / 10; value %= 10; pCur = new ListNode(value); if(pTail) { pTail->next = pCur; pTail = pCur; }else { pSum = pCur; pTail = pCur; } p = p->next; } if(carry) { pTail->next = new ListNode(carry); } return pSum; }
/*带头结点的情况 */ ListNode * Add(ListNode * head1,ListNode * head2) { ListNode* pSum = new ListNode(0); ListNode * pTail = pSum; ListNode * p1 = head1->next; ListNode * p2 = head2->next; ListNode * pCur = NULL; int carry = 0; int value = 0; while(p1&& p2) { value = carry + p1->value + p2->value; carry = value / 10; value %= 10; pCur = new ListNode(value); pTail->next = pCur; pTail = pCur; p1= p1->next; p2= p2->next; } ListNode * p = p1? p1: p2; while(p) { value = p->value +carry; carry = value / 10; value %= 10; pCur = new ListNode(value); pTail->next = pCur; pTail = pCur; p = p->next; } if(carry) { pTail->next = new ListNode(carry); } return pSum; }
3 链表部分翻转
给定一个链表，翻转该链表从m到n的位置，要求直接翻转而非申请新空间
如 1->2->3->4->5 m=2,n=4 返回 1->4->3->2->5
/*带头结点*/ void Reverse(ListNode * pHead,int from,int to) { ListNode* pCur = pHead->next; int i; for(i=0;i<from-1;i++) { pHead = pCur; pCur = pCur->next; } ListNode* pPre = pCur; pCur = pCur->pNext; to--; ListNode * pNext; for(;i<to;i++) { pNext = pCur->pNext; pCur->pNext = pHead->pNext; pHead->pNext = pCur; pPre->pNext = pNext; pCur = pNext; } } /*不用头结点 */ void Reverse(ListNode ** head,int from,int to) { if(head == NULL) return; ListNode * pCur = *head; ListNode * pHead = *head; int i; for(i = 0; i < from - 1; i++) { pHead = pCur; pCur = pCur->next; } ListNode * pPre = pCur; pCur = pCur->next; ListNode * pNext; for(; i < to-1; i++) { pNext = pCur->next; pCur->next = pHead->next; pHead->next = pCur; pPre->next = pNext; pCur = pNext; } }
4 链表划分(思考快排)
给定一个链表和一个值x,将链表划分为两部门，使得划分后小于x的节点在前，大于x的结点在后，在这两部分中要保持原链表中的出现顺序
/*带头结点*/ void Partition(ListNode * pHead, int pivotkey) { ListNode * pLeft = new ListNode(0); ListNode * pRight = new ListNode(0); ListNode * left = pLeft; ListNode * right = pRight; ListNode * p = pHead->next; while(p) { if(p->value < pivotkey) { left->next = p; left = p; }else { right->next = p; right = p; } p = p->next; } left->next = pRight->next; right->next = NULL: pHead->next = pLeft->next; delete pLeft; delete pRight; }
5 链表环入口
一个链表中包含环，如何找出环的入口结点
如图 找到3
ListNode* MeetingNode(ListNode* pHead) { if(pHead == NULL) return NULL; ListNode* pSlow = pHead->m_pNext; if(pSlow == NULL) return NULL; ListNode* pFast = pSlow->m_pNext; while(pFast != NULL && pSlow != NULL) { if(pFast == pSlow) return pFast; pSlow = pSlow->m_pNext; pFast = pFast->m_pNext; if(pFast != NULL) pFast = pFast->m_pNext; } return NULL; } ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode* meetingNode = MeetingNode(pHead); if(meetingNode == NULL) return NULL; // get the number of nodes in loop int nodesInLoop = 1; ListNode* pNode1 = meetingNode; while(pNode1->m_pNext != meetingNode) { pNode1 = pNode1->m_pNext; ++nodesInLoop; } // move pNode1 pNode1 = pHead; for(int i = 0; i < nodesInLoop; ++i) pNode1 = pNode1->m_pNext; // move pNode1 and pNode2 ListNode* pNode2 = pHead; while(pNode1 != pNode2) { pNode1 = pNode1->m_pNext; pNode2 = pNode2->m_pNext; } return pNode1; }
6 两个链表的第一个公共节点
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) { // 得到两个链表的长度 unsigned int nLength1 = GetListLength(pHead1); unsigned int nLength2 = GetListLength(pHead2); int nLengthDif = nLength1 - nLength2; ListNode* pListHeadLong = pHead1; ListNode* pListHeadShort = pHead2; if(nLength2 > nLength1) { pListHeadLong = pHead2; pListHeadShort = pHead1; nLengthDif = nLength2 - nLength1; } // 先在长链表上走几步，再同时在两个链表上遍历 for(int i = 0; i < nLengthDif; ++ i) pListHeadLong = pListHeadLong->m_pNext; while((pListHeadLong != NULL) && (pListHeadShort != NULL) && (pListHeadLong != pListHeadShort)) { pListHeadLong = pListHeadLong->m_pNext; pListHeadShort = pListHeadShort->m_pNext; } // 得到第一个公共结点 ListNode* pFisrtCommonNode = pListHeadLong; return pFisrtCommonNode; } unsigned int GetListLength(ListNode* pHead) { unsigned int nLength = 0; ListNode* pNode = pHead; while(pNode != NULL) { ++ nLength; pNode = pNode->m_pNext; } return nLength; }
7 链表倒数第K个节点
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(pListHead == NULL || k == 0) return NULL; ListNode *pAhead = pListHead; ListNode *pBehind = NULL; for(unsigned int i = 0; i < k - 1; ++ i) { if(pAhead->m_pNext != NULL) pAhead = pAhead->m_pNext; else { return NULL; } } pBehind = pListHead; while(pAhead->m_pNext != NULL) { pAhead = pAhead->m_pNext; pBehind = pBehind->m_pNext; } return pBehind; }
8 删除重复节点
1->2->3->3->4->4->5 变成 1->2->5
void deleteDuplication(ListNode** pHead) { if(pHead == NULL || *pHead == NULL) return; ListNode* pPreNode = NULL; ListNode* pNode = *pHead; while(pNode != NULL) { ListNode *pNext = pNode->m_pNext; bool needDelete = false; if(pNext != NULL && pNext->m_nValue == pNode->m_nValue) needDelete = true; if(!needDelete) { pPreNode = pNode; pNode = pNode->m_pNext; } else { int value = pNode->m_nValue; ListNode* pToBeDel = pNode; while(pToBeDel != NULL && pToBeDel->m_nValue == value) { pNext = pToBeDel->m_pNext; delete pToBeDel; pToBeDel = NULL; pToBeDel = pNext; } if(pPreNode == NULL) *pHead = pNext; else pPreNode->m_pNext = pNext; pNode = pNext; } } }
思考
8中 保留第一个重复的节点 ？
头插法
链表头结点的作用 思考