真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

關(guān)于鏈表的問題-創(chuàng)新互聯(lián)

關(guān)于鏈表

創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括菏澤網(wǎng)站建設(shè)、菏澤網(wǎng)站制作、菏澤網(wǎng)頁制作以及菏澤網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，菏澤網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到菏澤省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

   鏈表是一種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)，因?yàn)樵趧?chuàng)建鏈表時(shí)無需知道鏈表的長度，當(dāng)插入一個(gè)節(jié)點(diǎn)時(shí)，只需要為新的節(jié)點(diǎn)分配內(nèi)存，其空間效率和數(shù)組相比要高，但是每次都要?jiǎng)?chuàng)建空間所以時(shí)間不是很高

單向鏈表定義節(jié)點(diǎn)

struct ListNode
{
    int m_value;
    ListNode* m_pNext;
};

在鏈表后面添加節(jié)點(diǎn)

void AddToTail(ListNode** pHead,int value)//時(shí)間效率O(N)
{
    ListNode* pnewNode=new ListNode();//創(chuàng)建新結(jié)點(diǎn)
    pnewNode->m_value=value;
    pnewNode->m_pNext=NULL;
    
   if(pHead==NULL)//當(dāng)頭結(jié)點(diǎn)為空
    {
        pHead=pnewNode;
    }   
    else//不為空
    {
        ListNode*pNode=*pHead;
        
        while(pNode->m_next!=NULL)//遍歷找到最后一個(gè)節(jié)點(diǎn)
        {
            pNode=pNode->m_next;
        }
        pNode->m_next=pnewNode;
    }
}

刪除其中某節(jié)點(diǎn)

void RemoveNode(ListNode**pHead, int value)
{
	if (pHead == NULL||*pHead==NULL)//頭結(jié)點(diǎn)為空
		return;
	ListNode*pDelete = NULL;
	
	if ((*pHead)->m_value == value)
	{
		pDelete = *pHead;
		*pHead = (*pHead)->m_pNext;
	}
	else
	{
		ListNode*pNode = *pHead;
		//遍歷查找要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
		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：

   輸入一個(gè)鏈表頭結(jié)點(diǎn)，從頭到尾反過來打印這個(gè)結(jié)點(diǎn)值（不改變結(jié)點(diǎn)結(jié)構(gòu)）

程序1.0

   若鏈表為空直接返回鏈表，若只有一個(gè)節(jié)點(diǎn)，打印此結(jié)點(diǎn)；若有多個(gè)結(jié)點(diǎn)，設(shè)置一個(gè)計(jì)數(shù)器，先、遍歷結(jié)點(diǎn)統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)，再循環(huán)結(jié)點(diǎn)數(shù)次，在這個(gè)循環(huán)里再依次找到倒數(shù)第一個(gè)、倒數(shù)第二個(gè)、倒數(shù)第N個(gè)節(jié)點(diǎn)

void PrintListReverse(ListNode*pHead)//時(shí)間復(fù)雜度O（N^2）
{
	while (pHead == NULL)//沒有結(jié)點(diǎn)
		return;
	
	if (pHead->m_pNext == NULL)//一個(gè)節(jié)點(diǎn)
	{
		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個(gè)節(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
			
		}
		cout << pNode->m_value << "->";
		count--;
	}
}

程序2.0

   上面用循環(huán)實(shí)現(xiàn)，過于復(fù)雜且效率不高，所以第二次使用棧來完成，棧有“先入后出”的特性，所以用棧來實(shí)現(xiàn)更為方便，沒遇到一個(gè)不為空的結(jié)點(diǎn)就把它放到棧中

void PrintListReverse(ListNode*pHead)//時(shí)間復(fù)雜度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

   我們知道遞歸的本質(zhì)就是棧，所以我們也可以用棧來實(shí)現(xiàn)它，先遞歸后面的結(jié)點(diǎn)，一直遞歸到?jīng)]有結(jié)點(diǎn)，再輸出該結(jié)點(diǎn)

void PrintListReverse(ListNode*pHead)
{
	if (pHead != NULL)
	{	
		if (pHead->m_pNext != NULL)//遞歸停止條件
		{
			PrintListReverse(pHead->m_pNext);
		}
		cout << pHead->m_value << "->";
	}
}

   遞歸寫法雖然看起來要簡潔的多，但是若結(jié)點(diǎn)超級(jí)長則會(huì)導(dǎo)致函數(shù)調(diào)用棧溢出，所以在實(shí)現(xiàn)是最好使用顯示調(diào)用棧的方式來實(shí)現(xiàn)

題目2：

題目：在O（1）的時(shí)間刪除鏈表結(jié)點(diǎn)

分析：要?jiǎng)h除一個(gè)節(jié)點(diǎn)，O（n）的方法是從頭到尾遍歷找到要?jiǎng)h除的結(jié)點(diǎn)（即順序查找），并在鏈表中刪除它。

程序1.0 刪除一個(gè)節(jié)點(diǎn)復(fù)雜度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

刪除一個(gè)結(jié)點(diǎn)復(fù)雜度O（1），找到要?jiǎng)h除的結(jié)點(diǎn)pToBeDelete的后面的結(jié)點(diǎn)del，把這個(gè)結(jié)點(diǎn)的值覆蓋要?jiǎng)h除的結(jié)點(diǎn)，刪除這個(gè)后面的結(jié)點(diǎn)

void DeleteNode(ListNode**pListHead, ListNode* pToBeDeleted)
{
    if (pListHead || pToBeDeleted)//若為空
        return;
    if ((*pListHead == pToBeDeleted) && (pToBeDeleted->m_pNext == NULL))//只有一個(gè)節(jié)點(diǎn)且刪除這個(gè)結(jié)點(diǎn)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
        *pListHead = NULL;
        return;
    }
    if (pToBeDeleted->m_pNext == NULL)//有多個(gè)結(jié)點(diǎn)pToBeDeleted為尾節(jié)點(diǎn)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)//有多個(gè)結(jié)點(diǎn)且pToDeleted不為尾
    {
        ListNode*del = pToBeDeleted->m_pNext;
        pToBeDeleted->m_value = del->m_value;
        pToBeDeleted->m_pNext = del->m_pNext;
       
        delete del;
        del = NULL;
    }
}

題目3：

輸入一個(gè)鏈表，輸出鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)

分析：定義兩個(gè)指針均指向頭，一個(gè)指針先走K步，另一個(gè)等第一個(gè)指針走k步后再和其一起走，知道第一個(gè)走到空時(shí)第二個(gè)指針即走到倒數(shù)第k個(gè)節(jié)點(diǎn)

考慮：1.輸入的頭結(jié)點(diǎn)是否為空，訪問空指針指向的內(nèi)存導(dǎo)致程序奔潰 2.鏈表的結(jié)點(diǎn)是否大于k 3.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.題目：求鏈表中間結(jié)點(diǎn)

設(shè)置指向頭的快、慢指針，快指針每次走兩步，慢的每次走一步，當(dāng)快指針走到末尾時(shí)，慢指針剛好在中間

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.判斷一個(gè)指針是否構(gòu)成環(huán)形

同上方法，如果帶環(huán)，則快指針一定會(huì)追上慢指針，若快指針走到了鏈尾（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：

反轉(zhuǎn)鏈表

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：

合并兩個(gè)排序的鏈表

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;
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。


文章名稱：關(guān)于鏈表的問題-創(chuàng)新互聯(lián)
文章位置：http://weahome.cn/article/dcgoec.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部