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