1 143 重排链表

笨方案一：利用线性表存储该链表，而后直接按顺序访问指定元素，重建该链表即可。
在这里插入图片描述

void reorderList(ListNode* head) {if(head == nullptr) return;vector<ListNode*> vec;while(head != nullptr){vec.push_back(head);head = head->next;}int i = 0;int j = vec.size() - 1;while(i < j){vec[i]->next = vec[j];++i;if (i == j) {break;}vec[j]->next = vec[i];--j;}vec[i]->next = nullptr;
}

方案二：寻找链表中点 + 链表逆序 + 合并链表
注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。

这样任务可划分为三步：

1.1 找到原链表的中点（「876. 链表的中间结点」）。

使用快慢指针找到链表的中间节点。
在这里插入图片描述

2.2 将原链表的右半端反转（「206. 反转链表」）

使用迭代法实现链表的反转。

3.3 交叉合并两个链表（与「21. 合并两个有序链表」思路不同）

保证l2的长度小于l1，这里的写法与21不同。
在这里插入图片描述

class Solution {
public:void reorderList(ListNode* head) {if(head == nullptr) return;ListNode* mid = middleNode(head);ListNode* reverse = reverseList(mid->next);mid->next = nullptr;   // 将链表切断mergeList(head, reverse);}ListNode* middleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while(fast->next != nullptr && fast->next->next != nullptr){fast = fast->next->next;slow = slow->next;}return slow;}ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = nullptr;while(cur != nullptr){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}void mergeList(ListNode* l1, ListNode* l2) {while(l2 != nullptr){ListNode* templ1 = l1->next;l1->next = l2;l1 = templ1;ListNode* templ2 = l2->next;l2->next = l1;l2 = templ2;}}};

与21相同的思路代码如下，注意返回值为ListNode*了

ListNode* mergeList(ListNode* l1, ListNode* l2) {ListNode* dummyhead = new ListNode(999);ListNode* cur = dummyhead;while(l1 != nullptr && l2 != nullptr){cur->next = l1;l1 = l1->next;cur = cur->next;cur->next = l2;l2 = l2->next;cur = cur->next;}if(l1 != nullptr) cur->next = l1;if(l2 != nullptr) cur->next = l2;return dummyhead->next;
}

3.4 补充 21 合并两个有序链表

在这里插入图片描述

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr) return list2;if(list2 == nullptr) return list1;ListNode* dummyhead = new ListNode(0);ListNode* cur = dummyhead;while(list1 != nullptr && list2 != nullptr) {if(list1->val < list2->val){cur->next = list1;cur = cur->next;list1 = list1->next;}else{cur->next = list2;cur = cur->next;list2 = list2->next;}}if(list1 != nullptr) cur->next = list1;if(list2 != nullptr) cur->next = list2;return dummyhead->next;
}

2 328 奇偶链表

在这里插入图片描述

while的退出条件是画图得出的

ListNode* oddEvenList(ListNode* head) {if(head == nullptr) return head;ListNode* odd = head;ListNode* even = head->next;ListNode* evenhead = even;while(even != nullptr && even->next != nullptr) {odd->next = even->next;    // 1even->next = odd->next->next;   // 2odd = odd->next;even = even->next;}odd->next = evenhead;return head;
}

3 单向链表

#include<iostream>using namespace std;class MyLinkedList {
public:struct ListNode {int val;ListNode* next;ListNode(int val) : val(val), next(nullptr) {}};MyLinkedList() {node_ = new ListNode(0);size_ = 0;}int get(int index) {if (index >= size_ || index < 0) return -1;ListNode* cur = node_;while (index--) {cur = cur->next;}cur = cur->next;return cur->val;}void addAtHead(int val) {ListNode* newNode = new ListNode(val);newNode->next = node_->next;node_->next = newNode;size_++;}void addAtTail(int val) {ListNode* newNode = new ListNode(val);ListNode* cur = node_;while (cur->next != nullptr) {cur = cur->next;}cur->next = newNode;size_++;}void addAtIndex(int index, int val) {if (index > size_ || index < 0) return; // index可以为size_ListNode* newNode = new ListNode(val);ListNode* cur = node_;while (index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;size_++;}void deleteAtIndex(int index) {if (index >= size_ || index < 0) return;ListNode* cur = node_;while (index--) {cur = cur->next;}ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;size_--;}void show() {ListNode* cur = node_->next;while (cur != nullptr) {cout << cur->val << " ";cur = cur->next;}cout << endl;}private:int size_;ListNode* node_;
};int main() {MyLinkedList link;link.addAtHead(7);link.addAtHead(2);link.addAtHead(1);link.addAtTail(8);link.show();link.deleteAtIndex(2);link.show();return 0;
}

4 双向链表

#include<iostream>using namespace std;struct Node {int data_;Node* pre_;Node* next_;Node(int data): data_(data), pre_(nullptr), next_(nullptr) {}Node(){pre_ = nullptr;next_ = nullptr;}    
};class DoubleLink {
public:DoubleLink() {head_ = new Node();}~DoubleLink() {Node* p = head_;while (p != nullptr) {head_ = head_->next_;delete p;p = head_;}}public:void insert_head(int val) {Node* node = new Node(val);node->next_ = head_->next_;node->pre_ = head_;if (head_->next_ != nullptr) head_->next_->pre_ = node;  //原来链表里有第一个节点  确认head后面一个不为空head_->next_ = node;}// 尾插法void InsertTail(int val) {Node* p = head_;while (p->next_ != nullptr) {p = p->next_;}Node* node = new Node(val);node->pre_ = p;p->next_ = node;}void Remove(int val) {Node* p = head_->next_;while (p != nullptr) {if (p->data_ == val) {p->pre_->next_ = p->next_;if (p->next_ != nullptr) p->next_->pre_ = p->pre_;delete p;return;} else {p = p->next_;}}}bool Find(int val) {Node* p = head_->next_;while (p != nullptr) {if (p->data_ == val) {return true;} else {p = p->next_;}}}void show() {Node* p = head_->next_;while (p != nullptr) {cout << p->data_ << " ";p = p->next_;}cout << endl;}
private:Node* head_;
};int main() {DoubleLink dlink;dlink.InsertTail(20);dlink.InsertTail(23);dlink.InsertTail(89);dlink.InsertTail(15);dlink.InsertTail(36);dlink.InsertTail(78);dlink.InsertTail(56);dlink.InsertTail(41);dlink.InsertTail(32);dlink.show();dlink.insert_head(200);dlink.show();dlink.Remove(200);dlink.show();dlink.Remove(78);dlink.show();return 0;
}

5 双向循环链表

#include<iostream>using namespace std;struct Node {int data_;Node* pre_;Node* next_;Node(int data): data_(data), pre_(nullptr), next_(nullptr) {}Node(){pre_ = nullptr;next_ = nullptr;}    
};class DoubleCircleLink {
public:DoubleCircleLink() {head_ = new Node();head_->next_ = head_;head_->pre_ = head_;}~DoubleCircleLink() {Node* p = head_->next_;while (p != head_) {head_->next_ = p->next_;p->next_->pre_ = head_;delete p;p = head_->next_;}delete head_;head_ = nullptr;}public:void insert_head(int val) {Node* node = new Node(val);node->next_ = head_->next_;node->pre_ = head_;if (head_->next_ != nullptr) head_->next_->pre_ = node;  //原来链表里有第一个节点  确认head后面一个不为空head_->next_ = node;}// 尾插法void InsertTail(int val) {Node* p = head_->pre_;Node* node = new Node(val);node->pre_ = p;p->next_ = node;node->next_ = head_;head_->pre_ = node;}void Remove(int val) {Node* p = head_->next_;while (p != head_) {if (p->data_ == val) {p->pre_->next_ = p->next_;p->next_->pre_ = p->pre_;delete p;return;} else {p = p->next_;}}}bool Find(int val) {Node* p = head_->next_;while (p != head_) {if (p->data_ == val) {return true;} else {p = p->next_;}}}void show() {Node* p = head_->next_;while (p != head_) {cout << p->data_ << " ";p = p->next_;}cout << endl;}
private:Node* head_;
};int main() {DoubleCircleLink dlink;dlink.InsertTail(20);dlink.InsertTail(23);dlink.InsertTail(89);dlink.InsertTail(15);dlink.InsertTail(36);dlink.InsertTail(78);dlink.InsertTail(56);dlink.InsertTail(41);dlink.InsertTail(32);dlink.show();dlink.insert_head(200);dlink.show();dlink.Remove(200);dlink.show();dlink.Remove(78);dlink.show();return 0;
}