剑指offer—

剑指offer——链表

  1 #include"stdio.h"
  2 #include"stdlib.h"
  3 #include"iostream"
  4 using namespace std;
  5 
  6 struct ListNode
  7 {
  8     int m_Value;
  9     ListNode* m_pNext;
 10 };
 11 
 12 ListNode* CreateListNode(int value)
 13 {
 14     ListNode* pNode=new ListNode();
 15     pNode->m_Value=value;
 16     pNode->m_pNext=nullptr;
 17 
 18     return pNode;
 19 }
 20 
 21 void ConnectListNodes(ListNode* pCurrent,ListNode* pNext)
 22 {
 23     if(pCurrent==nullptr)
 24     {
 25         cout<<"Error to connect two nodes."<<endl;
 26         exit(1);
 27     }
 28     pCurrent->m_pNext=pNext;
 29 }
 30 
 31 void PrintListNode(ListNode* pNode)
 32 {
 33     if(pNode==nullptr)
 34     {
 35         cout<<"The node is nullptr."<<endl;
 36     }
 37     else
 38     {
 39         cout<<"the value in node is: "<<pNode->m_Value<<endl;
 40     }
 41 }
 42 
 43 void PrintList(ListNode *pHead)
 44 {
 45     cout<<"PrintList starts."<<endl;
 46 
 47     ListNode* pNode=pHead;
 48     while(pNode!=nullptr)
 49     {
 50         cout<<pNode->m_Value<<" ";
 51         pNode=pNode->m_pNext;
 52     }
 53     cout<<endl<<"PrintList ends."<<endl;
 54 }
 55 
 56 void DestroyList(ListNode* pHead)
 57 {
 58     ListNode* pNode=pHead;
 59     while(pNode!=nullptr)
 60     {
 61         pHead=pHead->m_pNext;
 62         delete pNode;
 63         pNode=pHead;
 64     }
 65 }
 66 
 67 void AddToTail(ListNode** pHead,int value)
 68 {
 69     ListNode* pNode=CreateListNode(value);
 70     if(pHead==nullptr || *pHead==nullptr)
 71     {
 72         *pHead=pNode;
 73     }
 74     else
 75     {
 76         ListNode* pTemp=*pHead;
 77         while(pTemp->m_pNext!=nullptr)
 78             pTemp=pTemp->m_pNext;
 79         pTemp->m_pNext=pNode;
 80     }
 81 }
 82 
 83 void RemoveNode(ListNode** pHead,int value)
 84 {
 85     if(pHead == nullptr || *pHead == nullptr)
 86         return;
 87 
 88     ListNode* pToBeDeleted = nullptr;
 89     if((*pHead)->m_Value == value)
 90     {
 91         pToBeDeleted = *pHead;
 92         *pHead = (*pHead)->m_pNext;
 93     }
 94     else
 95     {
 96         ListNode* pNode = *pHead;
 97         while(pNode->m_pNext != nullptr && pNode->m_pNext->m_Value != value)
 98             pNode = pNode->m_pNext;
 99 
100         if(pNode->m_pNext != nullptr && pNode->m_pNext->m_Value == value)
101         {
102             pToBeDeleted = pNode->m_pNext;
103             pNode->m_pNext = pNode->m_pNext->m_pNext;
104         }
105     }
106 
107     if(pToBeDeleted != nullptr)
108     {
109         delete pToBeDeleted;
110         pToBeDeleted = nullptr;//防止指正悬挂
111     }
112 }
113 //O(1)复杂度
114 void DeleteNode(ListNode** pHead,ListNode* pToBeDeleted)
115 {
116     if(*pHead==nullptr || pToBeDeleted==nullptr)
117         return;
118     if(pToBeDeleted->m_pNext!=nullptr)
119     {
120         ListNode* pNext=pToBeDeleted->m_pNext;
121         pToBeDeleted->m_pNext=pNext->m_pNext;
122         pToBeDeleted->m_Value=pNext->m_Value;
123         delete pNext;
124         pNext=nullptr;
125     }
126     else if(pToBeDeleted==*pHead)
127     {
128         delete pToBeDeleted;
129         pToBeDeleted=nullptr;
130         *pHead=nullptr;
131     }
132     else
133     {
134         ListNode* pNode=*pHead;
135         while(pNode->m_pNext!=pToBeDeleted)
136             pNode=pNode->m_pNext;
137         pNode->m_pNext=nullptr;
138         delete pToBeDeleted;
139         pToBeDeleted=nullptr;
140     }
141 }
142 
143 ListNode* TheLastKthNode(ListNode* pHead,int k)
144 {
145     if(pHead==nullptr || k<=0)
146         return nullptr;
147     ListNode* quickNode=pHead;
148     ListNode* slowNode=pHead;
149     int cnt=1;
150     while(quickNode->m_pNext!=nullptr&&cnt<k)
151     {
152         quickNode=quickNode->m_pNext;
153         ++cnt;
154     }
155     if(cnt<k)
156         return nullptr;
157     while(quickNode->m_pNext!=nullptr)
158     {
159         quickNode=quickNode->m_pNext;
160         slowNode=slowNode->m_pNext;
161     }
162     return slowNode;
163 }
164 
165 ListNode* MeetingNode(ListNode* pHead)
166 {
167     if(pHead==nullptr)
168         return nullptr;
169     ListNode* quickNode=pHead;
170     ListNode* slowNode=pHead;
171 
172     while(quickNode->m_pNext!=nullptr&&quickNode->m_pNext->m_pNext!=nullptr)
173     {
174         quickNode=quickNode->m_pNext->m_pNext;
175         slowNode=slowNode->m_pNext;
176         if(quickNode==slowNode)
177             break;
178     }
179     if(quickNode!=slowNode)
180     {
181         return nullptr;
182     }
183     return slowNode;
184 }
185 
186 ListNode* EntryNodeOfLoop(ListNode* pHead)
187 {
188     ListNode* meetingNode=MeetingNode(pHead);
189     if(meetingNode==nullptr)
190         return nullptr;
191     int nodesInLoop=1;
192     ListNode* pTemp=meetingNode;
193     while(pTemp->m_pNext!=meetingNode)
194     {
195         pTemp=pTemp->m_pNext;
196         nodesInLoop++;
197     }
198     ListNode* quickNode=pHead;
199     ListNode* slowNode=pHead;
200     for(int i=0;i<nodesInLoop;i++)
201         quickNode=quickNode->m_pNext;
202     while(slowNode!=quickNode)
203     {
204         quickNode=quickNode->m_pNext;
205         slowNode=slowNode->m_pNext;
206     }
207     return slowNode;
208 }
View Code