92.反轉鏈表II
這道題需要1.找到位置left 2.在位置left開始，一前一后兩個指針反轉鏈表，代碼同206.反轉鏈表，直到后一個指針指向right 3.把反轉后的頭節點鏈接到left-1后面，把反轉后的鏈表尾節點指向right+1位置的節點
因為可能會反轉head指向的節點
所以需要重新構造一個頭節點指向head
防止頭節點位置改變
ListNode* dummy = new ListNode(0);dummy->next = head;
然后for循環先找到left
ListNode* pre = dummy;ListNode* cur=head;ListNode* next=nullptr;for(int i=1;i<=right;i++){if(i<left){pre=pre->next;cur=cur->next;}}
cur節點指向left位置的節點，使用反轉鏈表反轉直到cur指向right
ListNode* pre = dummy;ListNode* cur=head;ListNode* next=nullptr;for(int i=1;i<=right;i++){if(left<=i&&right>=i){ListNode* tmp=cur->next;cur->next=next;next=cur;cur=tmp;}else if(i<left){pre=pre->next;cur=cur->next;}}
接著鏈接頭尾和反轉鏈表
pre指向left-1的位置
pre的下一個指針，也就是反轉前的left位置，此時，該指針指向反轉鏈表的尾部
因此，將反轉鏈表的尾部指向right+1的位置，也就是cur
讓pre指向反轉鏈表頭節點，也就是next
pre->next->next = cur;pre->next = next;
143.重排鏈表
雙指針求中點+雙指針反轉鏈表
從開頭出發，快指針走兩步，慢指針走一步
快指針走到尾巴的時候，慢指針走到中點
ListNode* left=head;ListNode* right=head;if(head==NULL&&head->next==NULL)return;while(right->next!=NULL&&right->next->next!=NULL){right=right->next;right=right->next;left=left->next;}
在紙上模擬一下尋找的過程，我們就知道鏈表中無論是偶數個節點還是奇數個節點，left永遠指向左半邊鏈表的最后一個節點
接著我們反轉后半部分鏈表，也就是left->next的部分
使用一前一后兩個指針
后一個節點指向前一個節點
等節點指向鏈表尾部，就結束了
不過我們首先也要把前半段節點末尾改成指向NULL
ListNode* cur=left->next;left->next=NULL;ListNode* pre=NULL;while(cur!=NULL){ListNode* tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}
兩端鏈表都準備好了，接下來就是合并兩個鏈表
兩個指針分別指向兩個鏈表的頭節點
挨個合并
cur=pre;pre=head;while(pre!=NULL&&cur!=NULL){ListNode* tmp=pre->next;pre->next=cur;right=cur->next;cur->next=tmp;cur=right;pre=tmp;}
最后得到整個代碼
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:void reorderList(ListNode* head) {ListNode* left=head;ListNode* right=head;if(head==NULL&&head->next==NULL)return;while(right->next!=NULL&&right->next->next!=NULL){right=right->next;right=right->next;left=left->next;}ListNode* cur=left->next;left->next=NULL;ListNode* pre=NULL;while(cur!=NULL){ListNode* tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}cur=pre;pre=head;while(pre!=NULL&&cur!=NULL){ListNode* tmp=pre->next;pre->next=cur;right=cur->next;cur->next=tmp;cur=right;pre=tmp;}}
};
