建站
咨詢
售后
建站咨詢
新聞中心
關于鏈表
成都創(chuàng)新互聯(lián)專注于新賓企業(yè)網站建設,響應式網站建設,商城網站制作。新賓網站建設公司,為新賓等地區(qū)提供建站服務。全流程定制設計，專業(yè)設計，全程項目跟蹤，成都創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務
鏈表是一種動態(tài)的數(shù)據(jù)結構，因為在創(chuàng)建鏈表時無需知道鏈表的長度，當插入一個節(jié)點時，只需要為新的節(jié)點分配內存，其空間效率和數(shù)組相比要高，但是每次都要創(chuàng)建空間所以時間不是很高
單向鏈表定義節(jié)點
struct ListNode
{
int m_value;
ListNode* m_pNext;
};在鏈表后面添加節(jié)點
void AddToTail(ListNode** pHead,int value)//時間效率O(N)
{
ListNode* pnewNode=new ListNode();//創(chuàng)建新結點
pnewNode->m_value=value;
pnewNode->m_pNext=NULL;
if(pHead==NULL)//當頭結點為空
{
pHead=pnewNode;
}
else//不為空
{
ListNode*pNode=*pHead;
while(pNode->m_next!=NULL)//遍歷找到最后一個節(jié)點
{
pNode=pNode->m_next;
}
pNode->m_next=pnewNode;
}
}刪除其中某節(jié)點
void RemoveNode(ListNode**pHead, int value)
{
if (pHead == NULL||*pHead==NULL)//頭結點為空
return;
ListNode*pDelete = NULL;
if ((*pHead)->m_value == value)
{
pDelete = *pHead;
*pHead = (*pHead)->m_pNext;
}
else
{
ListNode*pNode = *pHead;
//遍歷查找要刪除結點的前一個結點
while (pNode->m_pNext!=NULL &&pNode->m_pNext-> m_value != value)
{
pNode = pNode->m_pNext;
}
pDelete = pNode->m_pNext;
pNode->m_pNext = pDelete->m_pNext;
if (pDelete != NULL)
{
delete pDelete;
pDelete = NULL;
}
}題目1：
輸入一個鏈表頭結點，從頭到尾反過來打印這個結點值（不改變結點結構）
程序1.0
若鏈表為空直接返回鏈表，若只有一個節(jié)點，打印此結點；若有多個結點，設置一個計數(shù)器，先、遍歷結點統(tǒng)計結點個數(shù)，再循環(huán)結點數(shù)次，在這個循環(huán)里再依次找到倒數(shù)第一個、倒數(shù)第二個、倒數(shù)第N個節(jié)點
void PrintListReverse(ListNode*pHead)//時間復雜度O（N^2）
{
while (pHead == NULL)//沒有結點
return;
if (pHead->m_pNext == NULL)//一個節(jié)點
{
cout << pHead->m_value;
return;
}
ListNode*pNode = pHead;
int count =1;
while (pNode->m_pNext != NULL)
{
count++;
pNode = pNode->m_pNext;
}
while (count != 0)
{
for (int i = 1; i < count; i++)
{
pNode = pNode->m_pNext;//找到倒數(shù)第N個節(jié)點的前一個結點
}
cout << pNode->m_value << "->";
count--;
}
}程序2.0
上面用循環(huán)實現(xiàn)，過于復雜且效率不高，所以第二次使用棧來完成，棧有“先入后出”的特性，所以用棧來實現(xiàn)更為方便，沒遇到一個不為空的結點就把它放到棧中
void PrintListReverse(ListNode*pHead)//時間復雜度O(N)
{
stack s1;
ListNode*pNode = pHead;
while (pNode->m_pNext != NULL)
{
s1.push(pNode);
pNode = pNode->m_pNext;
}
while (!s1.empty())
{
cout << s1.top()->m_value << "->";
s1.pop();
}
} 程序3.0
我們知道遞歸的本質就是棧，所以我們也可以用棧來實現(xiàn)它，先遞歸后面的結點，一直遞歸到沒有結點，再輸出該結點
void PrintListReverse(ListNode*pHead)
{
if (pHead != NULL)
{
if (pHead->m_pNext != NULL)//遞歸停止條件
{
PrintListReverse(pHead->m_pNext);
}
cout << pHead->m_value << "->";
}
}
遞歸寫法雖然看起來要簡潔的多，但是若結點超級長則會導致函數(shù)調用棧溢出，所以在實現(xiàn)是最好使用顯示調用棧的方式來實現(xiàn)
題目2：
題目：在O（1）的時間刪除鏈表結點
分析：要刪除一個節(jié)點，O（n）的方法是從頭到尾遍歷找到要刪除的結點（即順序查找），并在鏈表中刪除它。
程序1.0 刪除一個節(jié)點復雜度O（n）
void DeleteNode(ListNode**pListHead, ListNode* pToBeDeleted)
{
if (pListHead || pToBeDeleted)
return;
ListNode*cur = *pListHead;
while (cur->m_pNext != pToBeDeleted)
{
cur = cur->m_pNext;
}
cur->m_pNext = pToBeDeleted->m_pNext;
delete pToBeDeleted;
}程序2.0
刪除一個結點復雜度O（1），找到要刪除的結點pToBeDelete的后面的結點del，把這個結點的值覆蓋要刪除的結點，刪除這個后面的結點
void DeleteNode(ListNode**pListHead, ListNode* pToBeDeleted)
{
if (pListHead || pToBeDeleted)//若為空
return;
if ((*pListHead == pToBeDeleted) && (pToBeDeleted->m_pNext == NULL))//只有一個節(jié)點且刪除這個結點
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pListHead = NULL;
return;
}
if (pToBeDeleted->m_pNext == NULL)//有多個結點pToBeDeleted為尾節(jié)點O(N)
{
ListNode*cur = *pListHead;
while (cur->m_pNext != pToBeDeleted)
{
cur = cur->m_pNext;
}
cur->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
else if (pToBeDeleted->m_pNext)//有多個結點且pToDeleted不為尾
{
ListNode*del = pToBeDeleted->m_pNext;
pToBeDeleted->m_value = del->m_value;
pToBeDeleted->m_pNext = del->m_pNext;
delete del;
del = NULL;
}
}題目3：
輸入一個鏈表，輸出鏈表中倒數(shù)第K個節(jié)點
分析：定義兩個指針均指向頭，一個指針先走K步，另一個等第一個指針走k步后再和其一起走，知道第一個走到空時第二個指針即走到倒數(shù)第k個節(jié)點
考慮：1.輸入的頭結點是否為空，訪問空指針指向的內存導致程序奔潰2.鏈表的結點是否大于k3.k若為0怎么辦
ListNode* FindKthToTail(ListNode*pHead, int k)
{
if (pHead == NULL || k == 0)
return NULL;
ListNode *fast = pHead;
ListNode*slow = pHead;
while (--k)
{
if (fast->m_pNext != NULL)
fast = fast->m_pNext;
else
return NULL;
}
while (fast->m_pNext)
{
slow = slow->m_pNext;
fast = fast->m_pNext;
}
return slow;
}相似快慢指針問題
1.題目：求鏈表中間結點
設置指向頭的快、慢指針，快指針每次走兩步，慢的每次走一步，當快指針走到末尾時，慢指針剛好在中間
ListNode*FindMidNode(ListNode*pHead)
{
if (pHead == NULL)
return NULL;
ListNode*fast = pHead;
ListNode*slow = pHead;
while (fast->m_pNext&&fast)
{
fast = fast->m_pNext->m_pNext;
slow = slow->m_pNext;
}
return slow;
}2.判斷一個指針是否構成環(huán)形
同上方法，如果帶環(huán)，則快指針一定會追上慢指針，若快指針走到了鏈尾（NULL），則不是環(huán)形鏈表
ListNode*IsCircleList(ListNode*pHead)
{
if (pHead == NULL)
return NULL;
ListNode*fast = pHead;
ListNode*slow = pHead;
while (fast&&fast->m_pNext)
{
fast = fast->m_pNext->m_pNext;
slow = slow->m_pNext;
if (slow == fast)
return slow;
}
return NULL;
}題目4：
反轉鏈表
void ReverseList(ListNode*pHead)
{
if (pHead == NULL||pHead->m_pNext==NULL)
return;
ListNode*newHead = NULL;
ListNode*cur = pHead;
ListNode*prev = pHead;
while (cur)
{
prev = cur;
cur = cur->m_pNext;
prev->m_pNext = newHead;
newHead = prev;
}
pHead = newHead;
}題目5：
合并兩個排序的鏈表
ListNode*Merge(ListNode*pHead1, ListNode*phead2)
{
if (pHead1 == NULL)
return phead2;
if (phead2 == NULL)
return pHead1;
ListNode*newHead = NULL;
while (pHead1&&phead2)
{
if (pHead1->m_value < phead2->m_value)
{
newHead = pHead1;
newHead->m_pNext = Merge(pHead1->m_pNext, phead2);
}
else
{
newHead = phead2;
newHead->m_pNext = Merge(pHead1, phead2->m_pNext);
}
}
return newHead;
}
新聞標題：關于鏈表的問題
本文URL：http://ef60e0e.cn/article/psjsss.html
