學(xué)習(xí)單鏈表已經(jīng)有一段日子了，從大二到現(xiàn)在，也有不少年，最近準(zhǔn)備實(shí)習(xí)生招聘，要開始復(fù)習(xí)并記錄一些重要知識(shí)。
鏈表逆置，一直是我記不住的一個(gè)內(nèi)容，如果要逆置一個(gè)數(shù)組或者vector，最簡單暴力的方法是可以從后往前迭代一次將值插入到新的容器中。但是普通單鏈表并不具備隨機(jī)訪問和從后往前迭代的能力，這也就給逆置帶來了一定的麻煩，需要一些操作。
逆置鏈表有兩種情況： 1.整個(gè)單鏈表逆置。例如：1->2->3->4 ==>4->3->2->1 2.逆置單鏈表的部分。例如：1->2->3->4 ==>1->3->2->4
需要一種能夠自己想到理解的方法，畢竟以前總是及記代碼，背算法；鄒博老師課中就提到了：頭插法
頭插法有一個(gè)特性：后插入的節(jié)點(diǎn)總是更靠近頭節(jié)點(diǎn)，優(yōu)雅地完成了逆置，因此我們將原鏈表逆置的方法就是遍歷一遍并用頭插法重新插入一次。
從頭開始遍歷，把鏈表中的每個(gè)節(jié)點(diǎn)頭插到新鏈表中。 假設(shè)我們的原鏈表是(0表示頭結(jié)點(diǎn))： 0->1->2->3->4->NULL 頭插法的基本過程是：
p->next=head->next;head->next=p;根據(jù)頭插法的思路，還需要遍歷原鏈表，為此設(shè)置三個(gè)指針：PRe表待頭插節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，cur表示待頭插的節(jié)點(diǎn)，next表示待頭插的節(jié)點(diǎn)。
設(shè)置next指針的原因是因?yàn)樵陬^插過程中，cur->next=head->next，鏈表就斷掉了，使用next記錄一下以便下次迭代時(shí)更新cur指針。
按照上面的例子，如果要逆置整個(gè)鏈表，需要將鏈表的第2個(gè)節(jié)點(diǎn)到最后一個(gè)節(jié)點(diǎn)頭插到head節(jié)點(diǎn)之后。對(duì)于 0->1->2->3->4->NULL 來說，要從2開始將元素依次頭插到0之后。
ListNode* reverseList(ListNode* head){ if(head==NULL) return head; ListNode*newhead=new ListNode(0);//創(chuàng)建頭結(jié)點(diǎn) newhead->next=head; ListNode*pre = newhead->next;//原鏈表第一個(gè)元素 ListNode*cur = pre->next;//原鏈表第二個(gè)元素 ListNode*next = NULL; while (cur != NULL) { next = cur->next;//記錄next元素 cur->next = newhead->next;//頭插 newhead->next = cur;//頭插//原cur節(jié)點(diǎn)被頭插到新鏈表，將斷開的鏈表連起來 pre->next = next; cur = next; } return newhead->next;}一樣的思路，假設(shè)我們要逆置 0->1->2->3->4->5->NULL 中的2->3->4 首先要找到head節(jié)點(diǎn)，這里是1。 再設(shè)置pre指針，這里是2 再設(shè)置cur指針，這里是3 然后將3->4頭插到1的位置。
ListNode* reverseBetween(ListNode* head, int start, int end) { ListNode *result=new ListNode(0);//頭結(jié)點(diǎn) result->next=head; ListNode*pre=result; ListNode *cur=result->next; ListNode *post = NULL; int n = start; while (--n) { pre = pre->next;//找到起始位置 } ListNode*newHead = pre; pre = pre->next; cur = pre->next; n = end-start;//設(shè)置要逆置的元素個(gè)數(shù) while (n--) { post = cur->next;//保存next cur->next = newHead->next;//頭插 newHead->next = cur;//頭插 pre->next = post;//將斷開的鏈表連起來 cur = post; } return result->next; }刪除重復(fù)節(jié)點(diǎn)的前提是鏈表有序，也有兩種情況，一種是重復(fù)的節(jié)點(diǎn)只保留一個(gè)； 例如： 1->2->2->3 去重后變成： 1->2->3
一種是重復(fù)節(jié)點(diǎn)通通刪掉， 例如： 1->2->2->3 去重后變成： 1->3
也就是遍歷一遍記錄重復(fù)元素，并刪除，由于是有序鏈表因此是比較容易的操作，雖然比不上stl的unique和erase簡單。
//stl去重 vector<int>nums = { 2, 2, 4, 3, 3, 1, 6,6,6,6}; sort(nums.begin(), nums.end()); auto end_unique = unique(nums.begin(), nums.end()); nums.erase(end_unique,nums.end());依然使用三個(gè)指針 pre：記錄待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。 cur：記錄待刪除節(jié)點(diǎn)。 next：記錄待刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)（方便遍歷）。
ListNode* deleteDuplicates(ListNode* head) { ListNode*newhead=new ListNode(0); newhead->next=head; ListNode*pre=newhead; ListNode*cur=newhead->next; ListNode*next=NULL; while(NULL!=cur) { next=cur->next;//記錄next while(NULL!=next&&(cur->val==next->val))//重復(fù)節(jié)點(diǎn) { pre->next=next; delete cur; cur=next; next=cur->next; } pre=cur;//向后迭代 cur=next; } return newhead->next; }如果要將重復(fù)的節(jié)點(diǎn)通通刪掉，其實(shí)很簡單，按照上面的思路可以設(shè)置一個(gè)flag，發(fā)現(xiàn)有重復(fù)元素時(shí)將flag設(shè)置為true，當(dāng)flag為true時(shí)，多做一次刪除操作，將剩余的那個(gè)節(jié)點(diǎn)刪掉。
ListNode* deleteDuplicates(ListNode* head) { ListNode*newhead=new ListNode(0); newhead->next=head; ListNode*pre=newhead; ListNode*cur=newhead->next; ListNode*next=NULL; bool flag=false; while(NULL!=cur) { next=cur->next; flag=false; while(NULL!=next&&(cur->val==next->val)) { pre->next=next; delete cur; cur=next; next=cur->next; flag=true; } if(flag)//有重復(fù)元素再刪除一次 { pre->next=next; delete cur; cur=next; } else { pre=cur; cur=next; } } return newhead->next; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
