|
1.鏈表中環(huán)的入口節(jié)點(diǎn) 首先判斷頭指針是不是空的 2.翻轉(zhuǎn)鏈表 需要判斷鏈表是不是空的或者鏈表是不是只有一個(gè)節(jié)點(diǎn)，如果是的話(huà)，直接就輸出原來(lái)的鏈表了； 如果不是的話(huà)，翻轉(zhuǎn)利用循環(huán)來(lái)做，因?yàn)樾枰獙?dāng)前節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)，所以后一個(gè)節(jié)點(diǎn)需要先保存位置，也就是需要三個(gè)指針，一個(gè)pPre，一個(gè)pCur，一個(gè)pNext：先保存后一個(gè)節(jié)點(diǎn)，然后把當(dāng)前節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)，然后把當(dāng)前節(jié)點(diǎn)變成上一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)變成當(dāng)前節(jié)點(diǎn)；注意翻轉(zhuǎn)之后頭結(jié)點(diǎn)是原來(lái)的最后一個(gè)節(jié)點(diǎn)。 3.從尾到頭打印鏈表 思路（1）：可以先翻轉(zhuǎn)鏈表，再逐個(gè)輸出 思路（2）：這種具有“后進(jìn)先出”特性的，用棧比較容易，創(chuàng)建一個(gè)棧存放鏈表的節(jié)點(diǎn)，存放完之后從棧頂依次取出即可 4.兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn) 舉例子： 首先需要知道的是，兩個(gè)鏈表從公共節(jié)點(diǎn)開(kāi)始，之后的節(jié)點(diǎn)肯定都是一模一樣的； 可以先遍歷得到兩個(gè)鏈表各自的長(zhǎng)度，然后讓長(zhǎng)的那個(gè)先走比另一個(gè)長(zhǎng)出的步數(shù)，再同時(shí)走，判斷哪里相等哪里就是第一個(gè)公共節(jié)點(diǎn)了 5.鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn) 單向鏈表肯定是不能從后往前數(shù)的，這個(gè)跟上面有的類(lèi)似，既然知道是倒數(shù)第k個(gè)，那就兩個(gè)指針，讓一個(gè)先走k-1步，然后兩個(gè)同時(shí)走，判斷先走的那個(gè)到尾結(jié)點(diǎn)了，那后走的那個(gè)就是倒數(shù)第k個(gè)節(jié)點(diǎn)。 6.刪除鏈表中重復(fù)的節(jié)點(diǎn) 例如：1 2 3 3 4 4 5結(jié)果是1 2 5 首先需要判斷頭指針（第一個(gè)節(jié)點(diǎn)）和第二個(gè)節(jié)點(diǎn)是不是空的，如果是，返回頭指針就行了； 正常情況的時(shí)候，因?yàn)橛锌赡艽嬖趧h除第一個(gè)節(jié)點(diǎn)的情況，所以需要先重新創(chuàng)建一個(gè)頭指針ListNode* newHead = new ListNode(-1)，然后把這個(gè)頭指針賦初值指向原本的頭指針newHead->next = pHead； 然后需要三個(gè)指針來(lái)解決這個(gè)問(wèn)題，分別是pPre pCur pNext三個(gè)，pPre 賦初值newHead,pCur賦初值pHead, 利用當(dāng)前節(jié)點(diǎn)的循環(huán)來(lái)進(jìn)行：得判斷當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為空才進(jìn)入循環(huán)來(lái)查找和刪除，因?yàn)槔镱^要對(duì)節(jié)點(diǎn)進(jìn)行刪除，所以要先保存下一個(gè)節(jié)點(diǎn)，然后如果當(dāng)前節(jié)點(diǎn)等于下一個(gè)節(jié)點(diǎn)的值，因?yàn)檫€要繼續(xù)判斷下一位，來(lái)一個(gè)循環(huán)，只要下一個(gè)節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的值相等，就把pNext往后移一個(gè)，直到找到不相等的就退出這個(gè)查找的循環(huán)了；然后執(zhí)行刪除，也就是把上一個(gè)節(jié)點(diǎn)pPre的下一個(gè)節(jié)點(diǎn)變成pNext，當(dāng)前操作循環(huán)的節(jié)點(diǎn)變成pNext,然后再去循環(huán)判斷； 那如果當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的值不相等呢：指針往后挪，循環(huán)再判斷，也就是pPre = pCur；pCur = pCur->next。 最后返回新的頭結(jié)點(diǎn)newHead的下一個(gè)節(jié)點(diǎn)即可。 7.復(fù)制復(fù)雜的鏈表 分成三個(gè)步驟： /*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead == nullptr)
return nullptr;
//分成三個(gè)步驟：
//1.復(fù)制原始鏈表的任意節(jié)點(diǎn)N并創(chuàng)建新節(jié)點(diǎn)N'，把節(jié)點(diǎn)N'鏈接到節(jié)點(diǎn)N的后面
//2.設(shè)置復(fù)制出來(lái)的節(jié)點(diǎn)的random，假設(shè)原始鏈表上的N的random指向節(jié)點(diǎn)S，那么其對(duì)應(yīng)復(fù)制出來(lái)的N'是N的next指向
//的節(jié)點(diǎn)，同樣S'也是S的next指向的節(jié)點(diǎn)
//3.把整個(gè)鏈表根據(jù)奇數(shù)偶數(shù)分出兩個(gè)鏈表來(lái)，偶數(shù)的就是拷貝的鏈表
ClonedNode(pHead);
SetRandom(pHead);
return ReconnectNodes(pHead);
}
void ClonedNode(RandomListNode* pHead)
{
RandomListNode* pNode = pHead;
while(pNode != nullptr)
{
RandomListNode* newNode = new RandomListNode(0);//創(chuàng)建新節(jié)點(diǎn)
newNode->label = pNode->label;
newNode->next = pNode->next;
newNode->random = nullptr;
pNode->next = newNode;
pNode = newNode->next;
}
}
void SetRandom(RandomListNode* pHead)
{
RandomListNode* pNode = pHead;
while(pNode != nullptr)
{
RandomListNode* pCloned = pNode->next;
if(pNode->random != nullptr)//這一步判斷別忘了，如果為空，會(huì)造成程序癱瘓
pCloned->random = pNode->random->next;
else
pCloned->random = nullptr;
pNode = pCloned->next;//pNode往后移一位
}
}
RandomListNode* ReconnectNodes(RandomListNode* Head)
{
RandomListNode* pNode = Head;//循環(huán)操作
RandomListNode* pClonedHead = nullptr;
RandomListNode* pClonedNode = nullptr;//創(chuàng)建一個(gè)新節(jié)點(diǎn)，作為拷貝鏈表的頭結(jié)點(diǎn)
if(pNode != nullptr)
{
pClonedHead = pClonedNode = pNode->next;
pNode->next = pClonedNode->next;
pNode = pNode->next;
}
while(pNode != nullptr)
{
pClonedNode->next = pNode->next;
pClonedNode = pClonedNode->next;
pNode->next = pClonedNode->next;
pNode = pNode->next;
}
return pClonedHead;
}
};
?8.翻轉(zhuǎn)鏈表 給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)?k?個(gè)位置，其中?k?是非負(fù)數(shù)。 這個(gè)題說(shuō)是翻轉(zhuǎn)鏈表，其實(shí)就是改變了鏈表的頭尾節(jié)點(diǎn)而已。 （1）先判斷特殊情況，比如鏈表是否為空，是否只有一個(gè)元素，翻轉(zhuǎn)的k是否為0等，否則直接返回 （2）然后處理一般情況，得先遍歷一次得到鏈表的總長(zhǎng)度size，然后將鏈表首尾相接，成為一個(gè)循環(huán)鏈表 （3）根據(jù)size和k的關(guān)系，計(jì)算出循環(huán)鏈表循環(huán)的次數(shù)loot= size - (k%size); （4）然后進(jìn)行指針循環(huán)，之前的頭尾節(jié)點(diǎn)指針開(kāi)始移動(dòng)，次數(shù)為loop，直到移動(dòng)結(jié)束，原先的尾結(jié)點(diǎn)指針指向的為新鏈表的尾部，原先的頭結(jié)點(diǎn)指針指向的為新鏈表的頭部。 9.扁平化多級(jí)雙向鏈表 多級(jí)雙向鏈表中，除了指向下一個(gè)節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)指針之外，它還有一個(gè)子鏈表指針，可能指向單獨(dú)的雙向鏈表。這些子列表也可能會(huì)有一個(gè)或多個(gè)自己的子項(xiàng)，依此類(lèi)推，生成多級(jí)數(shù)據(jù)結(jié)構(gòu)，如下面的示例所示。 給你位于列表第一級(jí)的頭節(jié)點(diǎn)，請(qǐng)你扁平化列表，使所有結(jié)點(diǎn)出現(xiàn)在單級(jí)雙鏈表中。
? ?這題太經(jīng)典了！ /*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/
class Solution {
public:
vector<Node*> v;
//這題就是二叉樹(shù)的前序遍歷
//可以先前序遍歷，將所有節(jié)點(diǎn)放入容器中，然后再順序進(jìn)行前后連接
void dfs(Node* head)
{
if(head == nullptr)
return;
v.push_back(head);
dfs(head->child);
dfs(head->next);
}
Node* flatten(Node* head) {
dfs(head);//這樣就將所有的節(jié)點(diǎn)放入了容器中，按照前序的方式
int n = v.size();//得到容器中的節(jié)點(diǎn)數(shù)
for(int i=0;i<n;i )
{
if(i<n-1)
v[i]->next = v[i 1];
if(i>0)
v[i]->prev = v[i-1];
v[i]->child = nullptr;
}
return head;
}
};
? 10.判斷是不是回文鏈表 /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
//先判斷特殊情況
if(head == nullptr || head->next == nullptr)
return true;
//然后一般情況的判斷方式是：先找到鏈表的中點(diǎn)，然后翻轉(zhuǎn)后半部分，然后進(jìn)行比較
ListNode* fast = head;
ListNode* slow = head;
while(fast != nullptr)
{
slow = slow->next;
fast = fast->next? fast->next->next : fast->next;
}
//最后的slow為原來(lái)鏈表的中間節(jié)點(diǎn)，也是待會(huì)兒需要翻轉(zhuǎn)鏈表的頭結(jié)點(diǎn)
//fast則指向了nullptr
//然后需要進(jìn)行翻轉(zhuǎn)
ListNode* pPre = nullptr;
while(slow != nullptr)
{
ListNode* temp = slow->next;//存儲(chǔ)下一個(gè)節(jié)點(diǎn)
slow->next = pPre;
pPre = slow;
slow = temp;
}
//然后進(jìn)行判斷
while(pPre != nullptr && head != nullptr)
{
if(pPre->val != head->val)
return false;
pPre = pPre->next;
head = head->next;
}
return true;
}
};
?
?
tips：遇到鏈表為題時(shí)候的思考方式 （1）是否能用雙指針解決 （2）知否可以將一個(gè)指針先走幾步，再兩個(gè)同時(shí)走解決 （3）是否需要知道鏈表節(jié)點(diǎn)的個(gè)數(shù) （4）是否需要將鏈表變成循環(huán)鏈表處理 （5）考慮是否需要容器，容器可以放節(jié)點(diǎn)，容器的好處也是能知道鏈表的長(zhǎng)度 （6）找鏈表的中點(diǎn)、翻轉(zhuǎn)鏈表都是最基本的操作，在拔高的題目里頭有可能會(huì)用到 來(lái)源：https://www./content-4-774451.html |
|
|
來(lái)自： 印度阿三17 > 《開(kāi)發(fā)》
