5-123
數(shù)組中可以隨機(jī)訪問(wèn)，相反鏈表就不行
leetcode：206

反轉(zhuǎn)一個(gè)鏈表，鏈表如果沒(méi)有特別聲明，則節(jié)點(diǎn)的值不發(fā)生改變


一共需要三個(gè)指針：current指向當(dāng)前需要處理的指針
next指向當(dāng)前需要處理的元素的下一個(gè)元素的指針
pre保存修改之后鏈表指向的指針

首先實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)的反轉(zhuǎn)

然后將pre、cur、next進(jìn)行更新（向后移動(dòng)一個(gè)指針
pre更新為cur指針
cur更新為next指針
next由于本身的更新指向下一個(gè)元素的位置

然后再重復(fù)前面的操作：將cur指向pre指針，然后更新pre、cur、next指針

練習(xí)題：leetcode 92

using namespace std;struct ListNode{int val;ListNode *next;ListNode(int x) :val(x), next(NULL){} }; ListNode* creatLinkedList(int arr[], int n){if(n==0)return NULL;ListNode* head=new ListNode(arr[0]);ListNode* curNode=head;for(int i=1; i<n; i++){curNode->next=new ListNode(arr[i]);curNode=curNode->next;}return head; }void printLinkedList(ListNode* head){ListNode* curNode=head;while(curNode != NULL){cout<< curNode->val<<"->";curNode=curNode->next;}cout<<"NULL"<<endl;return;}void deleteLinkedList(ListNode* head){ListNode* curNode=head;while(curNode!=NULL){ListNode* DelNode=curNode;curNode=curNode->next;delete delNode;}return; } class Solution{pulic:ListNode* reverseList(ListNode* head){ListNode* pre=NULL;ListNode* cur=head;while(cur != NULL){ListNode* next=cur->next;cur->next=pre;pre=cur;cur=next;}return pre;//pre指向該鏈表的頭結(jié)點(diǎn) } };int main(){int arr[]={1,2,3,4,5};int n=sizeof(arr)/sizeof(int);//計(jì)算出arr數(shù)組中的長(zhǎng)度 ListNode* head=createLinkedList(arr,n);printLinkedList(head);ListNode* head2=Solution().reverseList(head);printLinkedList(head2);deleteLinkedList(head2);return 0; }

思考題：leetcode 83

leetcode86

leetcode 328題

設(shè)立鏈表的虛擬頭結(jié)點(diǎn)

舉例：如刪除3的元素



該邏輯對(duì)刪除最后一個(gè)元素依然使用，對(duì)刪除第一個(gè)元素不適用。

增加一個(gè)虛擬變量


練習(xí)題：leetcode 82

leetcode 21

5-4 5 6
leetcode 24

創(chuàng)建幾個(gè)指針去預(yù)先保留要處理的幾個(gè)節(jié)點(diǎn)

思考：可不可以不用next

練習(xí)題：leetcode 25

leetcode 147 為一個(gè)鏈表進(jìn)行插入排序

leetcode 148 SORT LIST
寫一個(gè)排序算法，用O(n *logn)的時(shí)間復(fù)雜度為一個(gè)鏈表進(jìn)行排序

自頂向上，自頂向下

雙指針技術(shù)
leetcode 19題

優(yōu)化之后：只遍歷一遍鏈表，p和q之間的距離一定，p之前有多少個(gè)點(diǎn)不確定，當(dāng)q移到NULL時(shí)停止。

總結(jié)

以上是生活随笔為你收集整理的玩转算法值面试-第五章 -在链表中穿针引线的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。