本文主要记录链表的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。
一、设计链表
707. 设计链表（中等难度）
class MyLinkedList {
public:
// 定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
private:
int _size;// 元素个数
LinkedNode* _dummyHead;// 虚拟头结点
public:
MyLinkedList() {
_dummyHead = new LinkedNode(0);
_size = 0;
}
int get(int index) {
if(index>(_size-1)||index<0) return -1;
// 查找第index个节点
LinkedNode* cur = _dummyHead->next;
while(index--)cur = cur->next;
return cur->val;
}
void addAtHead(int val) {
//在头部添加新节点
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
void addAtTail(int val) {
//在尾部添加新节点
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next!=nullptr)cur = cur->next;
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if (index>_size) return;
LinkedNode* newNode = new LinkedNode(val);
// 找到第index个节点
LinkedNode* cur = _dummyHead;
while(index--) cur = cur->next;
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if (index>=_size||index<0) return;
// 找到第index个节点
LinkedNode* cur = _dummyHead;
while(index--) cur = cur->next;
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
_size--;
}
};
382. 链表随机节点（中等难度）
class Solution {
vector<int> arr;// 将所有节点添加进一个数组中
public:
Solution(ListNode *head) {
while (head) {
arr.emplace_back(head->val);//高效添加
head = head->next;
}
}
int getRandom() {
return arr[rand()%arr.size()];
}
};
二、链表删除
1、删除链表中的特定值
203. 移除链表元素（简单难度）
剑指 Offer 18. 删除链表的节点（简单难度）
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//新建虚拟头结点
ListNode * myHead = new ListNode(0);
myHead->next=head;
//双指针
ListNode* prev=myHead;//慢指针负责删除节点
ListNode* cur=prev->next;//当前节点负责确定是否需要删除
while (cur) {
// 如果满足条件则执行删除操作；否则慢指针前进一步
if(cur->val == val) {
prev->next = cur->next;//删除快指针
} else {
prev = cur;//慢指针前进一步
}
cur = cur->next;//快指针前进一步
}
return myHead->next;
}
};
83. 删除排序链表中的重复元素（简单难度）
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// 新建虚拟头结点
ListNode * myHead=new ListNode(-101);
myHead->next=head;
// 快慢指针扫描单链表
ListNode * prev=myHead;//负责删除
ListNode * cur=head; // 负责遍历和确定
while(cur!=nullptr){
if(cur->val==prev->val){
prev->next=cur->next;
}
else{
prev=prev->next;
}
cur=cur->next;
}
return myHead->next;
}
};
2、只给出待删除元素，实现删除效果
237. 删除链表中的节点（简单难度）
面试题 02.03. 删除中间节点（简单难度）
class Solution {
public:
void deleteNode(ListNode* node) {
// node是要删除的节点，将其伪装成下一个节点son
ListNode* son=node->next;
node->val=son->val;//伪装其val
node->next=son->next;//伪装其next
}
};
3、删除链表中的倒数第N个节点
19. 删除链表的倒数第 N 个结点（中等难度）
剑指 Offer 22. 链表中倒数第k个节点（简单难度）
剑指 Offer II 021. 删除链表的倒数第 n 个结点（中等难度）
方式一：计数法
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
// 循环单链表获取len
int len=0;
ListNode* p=head;
while(p){
p=p->next;
len++;
}
// 循环单链表找到第len-k个元素（倒数第k个==正数第len-k+1）
int i=0;
p=head;
while(p&&i<len-k){
p=p->next;
i++;
}
return p;
}
};
方式二：快慢指针法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast=head;
ListNode* slow=head;
//先让fast走n步，此时fast可能不存在
for(int i=0;i<n;i++){
fast=fast->next;
}
//若fast不存在，说明n>链表的长度，则删除掉头结点，保留头结点之后的节点
if(!fast){
return head->next;
}
//若fast存在，同时遍历
while(fast->next){
slow=slow->next;
fast=fast->next;
}
slow->next=slow->next->next;
return head;
}
};
2095. 删除链表的中间节点（中等难度）
快慢指针法：
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
ListNode* p=head;
int len=0;
while(p){
p=p->next;
len++;
}
if(len==1) return nullptr;
if(len==2) {
head->next=nullptr;
return head;
}
int i=0;
p=head;
while(p&&i<len/2-1){
p=p->next;
i++;
}
p->next=p->next->next;
return head;
}
};
4、删除链表中的一段特殊序列
82. 删除排序链表中的重复元素 II（中等难度）
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// 新建虚拟头结点
ListNode * myHead=new ListNode(-101);
myHead->next=head;
// 快慢指针扫描单链表删除重复元素
ListNode* p=myHead;//遍历指针，负责遍历
ListNode * left,*right;//快慢指针，
while(p->next!=nullptr){
left=p->next;//保留起始指针
right=left; //一开始快慢指针相同，比p多一步
// 尝试移动right,如果right->next存在且和right相同就移动一步，最终right将指向最后一个相同的数
while(right->next && right->next->val==right->val)
right=right->next;
// 如果left==right，说明right没有移动，即没有相同值，p正常移动
if(left == right) p=p->next;
// 如果left!=right，说明right有移动，left和right所指的都是相同值
else p->next=right->next;
}
return myHead->next;
}
};
1171. 从链表中删去总和值为零的连续节点（中等难度）
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
// 新建虚拟头结点
ListNode* myHead=new ListNode(0);
myHead->next=head;
// 遍历
ListNode*p=myHead;
ListNode* left,* right;
while(p->next!=nullptr){
left=p->next;
right=left;
// 尝试移动right,记录left到right的和作为标准
int sum=left->val;//[left,right]的元素之和，
while(right->next){
// 如果sum为零则退出需要删除节点
if(sum==0) break;
// 如果sum不为零则继续累加直至表尾
else{
right = right->next;//right前进
sum += right->val;//right
}
}
if(sum!=0) p=p->next;// 如果sum不为零，p正常移动
else p->next=right->next; // 如果sum为零，p移动到right的右侧
}
return myHead->next;
}
};
三、链表反转
1、反转整个链表
206. 反转链表（简单难度）
剑指 Offer 24. 反转链表（简单难度）
剑指 Offer II 024. 反转链表（简单难度）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* left=nullptr;
ListNode* right=head;
while(right!=nullptr){
//保存
ListNode* temp=right->next;
//反转
right->next=left;
//更新
left=right;
right=temp;
}
return left;
}
};
2、反转单链表的某个区间
92. 反转链表 II（中等难度）
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
// 新建虚拟头结点
ListNode* myHead = new ListNode(0);
myHead->next = head;
// 慢指针先找到第left-1个节点
ListNode* slow=myHead;
int i=0;
while(slow&&i<left-1){
slow=slow->next;
i++;
}
if(slow==nullptr) return myHead->next;//说明链表没有要反转的区间，直接返回
// 慢指针和快指针一起反转[left,right]
ListNode* rhead=slow->next;//第left个节点（反转序列的头结点）
// 循环right-left次
for(int i=left;i<right;i++){
//保存
ListNode* temp=rhead->next;//保存rhead的后1步
rhead->next = temp->next;//rhead重新指向后2步
//反转
temp->next = slow->next;//rhead的后1步指向快指针
//更新
slow->next=temp;//慢指针指向rhead的后1步
}
// 更新头结点
return myHead->next;
}
};
3、判断是否是回文链表
234. 回文链表（简单难度）
剑指 Offer II 027. 回文链表（简单难度）
面试题 02.06. 回文链表（简单难度）
class Solution {
public:
//反转链表
ListNode* reverse(ListNode* head){
ListNode* pre=NULL;
ListNode* temp=NULL;
ListNode* cur=head;
while(cur){
temp=cur->next;
cur->next=pre;
pre = cur;
cur = temp;
}
head=pre;
return head;
}
bool isPalindrome(ListNode* head) {
// 特殊情况
if (head == NULL || head->next == NULL) {
return true;
}
ListNode* left=head;
ListNode* right=head;
//根据快慢指针找到中点，同时出发
while(right->next&&right->next->next){
right=right->next->next;//快指针走两步
left=left->next;//慢指针走一步
}
//反转链表的后半部分
right = reverse(left->next);//right指向后半部分头结点
left = head;//left指向前半部分头结点
//比较链表的前后两部分
while(right&&left){
if(right->val!=left->val){
return false;
}
right=right->next;
left=left->next;
}
return true;
}
};
四、链表相加
2. 两数相加（中等难度）
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// 新建结果链表的虚拟头结点
ListNode* myHead = new ListNode(0);
// 同时遍历2个可能不等长的链表
ListNode* cur = myHead;//遍历指针
int sum = 0;
bool carry = false;
while(l1 != NULL || l2 != NULL){
sum = 0;
// 获取链表1的值
if(l1 != NULL){
sum += l1->val;
l1 = l1 -> next;
}
// 获取链表2的值
if(l2 != NULL){
sum += l2->val;
l2 = l2 -> next;
}
// 如果需要进位则+1
if(carry) sum++;
// 为结果链表添加新的元素
cur -> next = new ListNode(sum % 10);//第一元素
cur = cur -> next;
carry = sum >= 10 ? true: false;//发现需要进位
}
//如果最后还需要+1位，则需要继续添加一个新结点
if(carry) cur -> next = new ListNode(1);
return myHead -> next;
}
};
445. 两数相加 II（中等难度）
剑指 Offer II 025. 链表中的两数相加（中等难度）
面试题 02.05. 链表求和（中等难度）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* slow=NULL;//慢指针
ListNode* fast=head;//快指针
while(fast!=NULL){
//保存
ListNode* temp = fast->next;
//反转
fast->next=slow;
//更新
slow=fast;
fast=temp;
}
//更新头结点
head=slow;
return head;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head=new ListNode(-1);//结果链表的虚拟头结点
ListNode* cur=head;//遍历指针
l1=reverseList(l1);
l2=reverseList(l2);
// 同时遍历2个链表
int sum=0;
bool carry=false;//是否需要进位
while(l1||l2){
sum=0;
if(l1!=nullptr){
sum+=l1->val;
l1=l1->next;
}
if(l2!=nullptr){
sum+=l2->val;
l2=l2->next;
}
if(carry) sum++;
// 为结果链表添加一个新的结果
cur->next=new ListNode(sum%10);
cur=cur->next;
carry = sum >= 10 ? true: false;//发现需要进位
}
if(carry) cur->next=new ListNode(1);
head->next = reverseList(head->next);
return head->next;
}
};
五、链表相交
1、找到2个单链表的相交点
160. 相交链表（简单难度）
面试题 02.07. 链表相交（简单难度）
剑指 Offer 52. 两个链表的第一个公共节点（简单难度）
剑指 Offer II 023. 两个链表的第一个重合节点（简单难度）
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA=headA;
ListNode *pB=headB;
// 获取两个单链表的长度
int lenA=0;
int lenB=0;
while(pA){
lenA++;
pA=pA->next;
}
while(pB){
lenB++;
pB=pB->next;
}
// 让长链表的遍历指针先走
pA=headA;
pB=headB;
if(lenA>lenB){
int gap=lenA-lenB;
while(gap--){
pA=pA->next;
}
}
else if(lenA<lenB){
int gap=lenB-lenA;
while(gap--){
pB=pB->next;
}
}
//长短链表同时开始走
while(pA&&pB){
if(pA==pB) return pA;
pA=pA->next;
pB=pB->next;
}
return NULL;
}
};
2、环形链表
876. 链表的中间结点（简单难度）
class Solution {
public:
ListNode* middleNode(ListNode* head) {
// 方法一：快慢指针
// ListNode* slow=head;
// ListNode* fast=head;
// while(slow&&fast&&fast->next){
// slow=slow->next;//2,3,4
// fast=fast->next->next;//3,5,null
// }
// return slow;
// 方法二：计数法
int len=0;
ListNode* p=head;
if(p==nullptr) return nullptr;
while(p){
p=p->next;
len++;
}
//
int i=0;
p=head;
while(p&&i<len/2){
p=p->next;
i++;
}
return p;
}
};
141. 环形链表（简单难度）
class Solution {
public:
bool hasCycle(ListNode *head) {
// 快慢指针
ListNode *fast=head;
ListNode *slow=head;
while(fast && fast->next){
slow=slow->next;
fast=fast->next->next;
if(slow==fast) return true; //指针相同说明相遇
}
return false;
}
};
142. 环形链表 II（中等难度）
剑指 Offer II 022. 链表中环的入口节点（中等难度）
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
// 快指针每次走2步，慢指针每次走1步，相遇即有环
while(fast && fast->next ) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，说明有环
if (slow == fast) {
slow=head;
// head和相遇点相同速度出发再次相遇的就是入口
while(fast&& slow) {
// 快慢指针第一次相遇，说明此时为入口
if (slow == fast) return slow;;
slow = slow->next;
fast = fast->next;
}
}
}
return NULL;
}
};
六、链表合并
1、合并有序链表
21. 合并两个有序链表（简单难度）
剑指 Offer 25. 合并两个排序的链表（简单难度）
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* result = new ListNode(-1); // 结果链表,默认第一个为虚拟头结点
ListNode* p = result;// 遍历指针，该指针会变化
// 同时遍历两2个链表
while(list1&&list2){
// 谁小将谁添加进结果链表
if(list1->val<=list2->val){
p->next=list1;
list1=list1->next;
}
else{
p->next=list2;
list2=list2->next;
}
p=p->next;
}
// 此时有个链表有剩余，继续添加
while(list1!=NULL){
p->next=list1;
list1=list1->next;
p=p->next;
}
while(list2!=NULL){
p->next=list2;
list2=list2->next;
p=p->next;
}
return result->next;
}
};
2、拼接链表
1669. 合并两个链表（中等难度）
class Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
// 找到list1的第a-1个节点
int i=0;
ListNode* pa=list1;
while(pa&&i<a-1){
pa=pa->next;
i++;
}
// 找到list1的第b个节点;
i=0;
ListNode* pb=list1;
while(pb&&i<b){
pb=pb->next;
i++;
}
// 找到list2的最后一个节点
ListNode* last=list2;
while(last->next){
last=last->next;
}
// 拼接两个链表
pa->next=list2;
last->next=pb->next;
return list1;
}
};
23. 合并K个升序链表（困难难度）
剑指 Offer II 078. 合并排序链表（困难难度）
class Solution {
public:
// 合并2个有序链表
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* result = new ListNode(-1); // 结果链表,默认第一个为虚拟头结点
ListNode* p = result;// 遍历指针，该指针会变化
// 同时遍历两2个链表
while(list1&&list2){
// 谁小将谁添加进结果链表
if(list1->val<=list2->val){
p->next=list1;
list1=list1->next;
}
else{
p->next=list2;
list2=list2->next;
}
p=p->next;
}
// 此时有个链表有剩余，继续添加
while(list1!=NULL){
p->next=list1;
list1=list1->next;
p=p->next;
}
while(list2!=NULL){
p->next=list2;
list2=list2->next;
p=p->next;
}
return result->next;
}
// 合并k个有序链表
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *ans = nullptr;
for (size_t i = 0; i < lists.size(); ++i) {
ans = mergeTwoLists(ans, lists[i]);// 调用合并2个有序链表
}
return ans;
}
};
七、循环链表
61. 旋转链表（中等难度）
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
// 空链表直接返回空
if(head==nullptr) return nullptr;
// 找到最后一个节点并统计len
ListNode* p=head;
int len=1;
while(p->next){
p=p->next;
len++;
}
// 如果k==len,直接返回
if(k==len){
return head;
}
// 如果k!=len,修改循环链表
else{
p->next=head;
}
// 找到第len-k个节点
p=head;
if(k>len) k=k%len;
int i=len-k-1;
while(i--){
p=p->next;
}
ListNode* res=p->next;//新的头结点
p->next=nullptr;//解除循环
return res;
}
};
剑指 Offer II 029. 排序的循环链表（中等难度）
思路：如果链表为空，直接新建结点，改变指针指向后返回即可；如果链表不空：先找到循环链表的尾巴，即最大值结点，找到了尾巴相当于也找到了最小值结点，因为tail->next就是最小的；判断插入值是否比最小值小或者比最大值大，如果满足，就插入到tail后面即可；如果插入值介于最小和最大之间，循环查找插入位置，当某个结点值比插入值小且那个结点的后一个结点比插入结点大时，即可插入。
class Solution {
public:
Node* insert(Node* head, int insertVal) {
Node* newNode = new Node(insertVal);
// 如果链表为空，直接新建节点，改变指针指向后返回
if(head==NULL){
newNode->next=newNode;
return newNode;
}
// 找到循环链表中的最大值,设为循环链表的尾部
Node* p=head->next;
Node* tail=head;
int max=head->val;
while(p!=head){
if(p->val>=max) {
max=p->val;
tail=p;
}
p=p->next;
}
// 如果插入值大于最小值或者小于最小值，插入tail之后即可
if(insertVal>max||insertVal<tail->next->val){
Node* temp =tail->next;//保存tail->next
tail->next=newNode;
newNode->next=temp;
}
else{
// 如果插入值介于最小值和最大值之间，则遍历寻找插入位置
while(p){
if(p->val<=insertVal&&p->next->val>=insertVal){
Node* temp =p->next;//保存p->next
p->next=newNode;//p指向新节点
newNode->next=temp;//新节点指向p->next
break;
}
p=p->next;
}
}
return head;
}
};
八、分隔链表
86. 分隔链表（中等难度）
面试题 02.04. 分割链表（中等难度）
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* small=new ListNode(0);
ListNode* pSmall=small;
ListNode* large=new ListNode(0);
ListNode* pLarge=large;
// 找出所有值比listNode小的
ListNode* p=head;
while(p){
if(p->val<x) {
pSmall->next=p;//添加一个新节点
pSmall=pSmall->next;//指针前进一步
}else{
pLarge->next=p;
pLarge=pLarge->next;
}
p=p->next;
}
pLarge->next=nullptr;//去除掉最后
pSmall->next=large->next;//拼接
return small->next;
}
};
328. 奇偶链表（中等难度）
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode* front=new ListNode(0);//结果链表的前部分,奇数
ListNode* curFront=front;
ListNode* back=new ListNode(0);//结果链表的后部分，偶数
ListNode* curBack=back;
// 遍历整个链表
ListNode* p=head;
bool flag=true;
while(p){
if(flag){
curFront->next=p;
curFront=curFront->next;
flag=false;
}else{
curBack->next=p;
curBack=curBack->next;
flag=true;
}
p=p->next;
}
// 将后链表的末尾去除
curBack->next=nullptr;
// 将前链表的末尾接上后链表
curFront->next=back->next;
return front->next;
}
};
九、链表复制
138. 复制带随机指针的链表（中等难度）
剑指 Offer 35. 复杂链表的复制（中等难度）
class Solution {
public:
/*难点：random可能指向未创建的节点*/
Node* copyRandomList(Node* head) {
if(head==NULL) return NULL;
// 第一步：遍历原始链表，创建新节点并且存入哈希表中
unordered_map<Node*,Node*> dict;//key:原有链表节点 value:新创建链表节点
Node* cur=head;
while(cur){
dict[cur]=new Node(cur->val);//存入哈希表
cur=cur->next;
}
// 第二步：遍历原始链表，修改哈希表中每个新节点的next指针和random指针
cur=head;
while(cur){
Node* curNewNode=dict[cur];// 获取当前节点对应的新节点
curNewNode->next=dict[cur->next];// 修改新节点的next指针
curNewNode->random=dict[cur->random]; // 修改新节点的random指针
// 循环前进
cur=cur->next;
}
return dict[head];
}
};
十、链表排序
1、链表中点+反转链表+合并链表
143. 重排链表（中等难度）
剑指 Offer II 026. 重排链表（中等难度）
class Solution {
public:
// 获取中间节点
ListNode* getMiddleNode(ListNode* head){
ListNode* slow=head;
ListNode* fast=head;
while(fast->next&&fast->next->next){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
// 反转整个链表
ListNode* reverseList(ListNode* head){
ListNode* left=nullptr;
ListNode* right=head;
while(right){
// 保存
ListNode* temp=right->next;
// 反转
right->next=left;
// 前进
left=right;
right=temp;
}
return left;
}
// 在l1链表中插入l2链表1,2 4,3 -》1,4,2 3
void mergeList(ListNode* l1,ListNode* l2){
ListNode* res=new ListNode(0);//结果链表的虚拟头结点
ListNode* p=res;
while(l1&&l2){
p->next=l1;
l1=l1->next;
p->next->next=l2;
l2=l2->next;
p=p->next->next;
}
// l1和l2可能是不等长的，有一个会多出一个元素
if(l1) p->next=l1;
if(l2) p->next=l2;
l1=res->next;
// ListNode* p1;
// ListNode* p2;
// while(l1&&l2){
// // 保存
// p1 = l1->next;//2
// p2 = l2->next;//3
// // 连接
// l1->next = l2;//1指向4
// l2->next = p1;//4指向2
// // 移动指针
// l1 = p1;//l1指向2
// l2 = p2;//l2指向3
// }
}
void reorderList(ListNode* head) {
if(head==nullptr) return;
// 寻找链表中点
ListNode* mid = getMiddleNode(head);
// 将链表分割为左右两部分
ListNode* l1 = head;
ListNode* l2 = mid->next;
mid->next = nullptr;//将l1和l2分割开
// 反转右半部分的链表
l2 = reverseList(l2);
// 将链表合并起来
mergeList(l1, l2);
}
};
2、调整相邻节点的顺序
24. 两两交换链表中的节点（中等难度）
方法一：
class Solution {
public:
// 方法：分隔链表+合并链表：
ListNode* swapPairs(ListNode* head) {
// 分隔链表：遍历一遍将奇数节点和偶数节点分开存放
ListNode* oddHead=new ListNode(0);//奇数元素所在链表
ListNode* pOdd=oddHead;
ListNode* evenHead=new ListNode(0);//偶数元素所在链表
ListNode* pEven=evenHead;
bool isOdd=true;
while(head){
if(isOdd){
pOdd->next=head;
pOdd=pOdd->next;
isOdd=false;
}else{
pEven->next=head;
pEven=pEven->next;
isOdd=true;
}
head=head->next;
}
pOdd->next=nullptr;
pEven->next=nullptr;
// 合并链表
ListNode* myHead=new ListNode(0);
ListNode* p=myHead;
pOdd=oddHead->next;
pEven=evenHead->next;
while(pEven&&pOdd){
p->next=pEven;
pEven=pEven->next;
p->next->next=pOdd;
pOdd=pOdd->next;
p=p->next->next;
}
if(pOdd) p->next=pOdd;
if(pEven) p->next=pEven;
return myHead->next;
}
};
方法二：指针法
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 新建虚拟头结点
ListNode* myHead=new ListNode(0);
myHead->next=head;
// 遍历指针
ListNode* cur=myHead;
while(cur->next&&cur->next->next){
// 新建指针
ListNode* slow=cur->next;
ListNode* fast=cur->next->next;
// 改变指向
cur->next=fast;//cur指向fast
slow->next=fast->next;//slow指向fast的后一位
fast->next=slow;//fast指向slow
// cur前进一步
cur=slow;
}
return myHead->next;
}
};
3、插入排序
147. 对链表进行插入排序（中等难度）
class Solution {
public:
// 从小到大排序，难点：插入算法的思想，搜索插入位置
ListNode* insertionSortList(ListNode* head) {
if(head==nullptr) return nullptr;
// 新建虚拟头结点
ListNode* myHead=new ListNode(0);
myHead->next=head;
// 双指针进行插入排序
ListNode* lastSorted=head;//最后一个排序好的节点
ListNode* cur=head->next;// 当前遍历到的节点
while(cur){
// 如果当前节点值>最后一个排序好的节点，直接+1
if(cur->val>=lastSorted->val){
lastSorted=lastSorted->next;
}
// 如果当前节点值<最后一个排序好的节点，从头遍历寻找插入位置
else{
ListNode* prev = myHead;//从虚拟头结点开始
// 遍历找到第一个prev->next的值大于cur的值
while (prev->next->val <= cur->val) {
prev = prev->next;
}
// 保存cur的后一个元素
lastSorted->next = cur->next;//排序好的节点+1
// 在prev后面插入cur
cur->next = prev->next;//当前节点
prev->next = cur;
}
cur = lastSorted->next;
}
return myHead->next;
}
};
4、归并排序
148. 排序链表（中等难度）
剑指 Offer II 077. 链表排序（中等难度）
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);//归并排序
}
// 分割2个单链表
ListNode* sortList(ListNode* head,ListNode* tail) {
// 如果头结点为空，直接返回
if(head==nullptr) return nullptr;
// 如果头结点的下一个节点就是尾结点，说明当前链表只有1个元素
if (head->next == tail) {
head->next = nullptr;
return head;
}
// 快慢指针找到head到tail的中间元素
ListNode* slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;//中间元素
ListNode* l1 = sortList(head, mid); // 将左半部分变为有序链表
ListNode* l2 = sortList(mid, tail); // 将右半部分变为有序链表
return mergeList(l1, l2);
}
// 合并2个单链表
ListNode* mergeList(ListNode* l1,ListNode* l2){
ListNode* myHead= new ListNode(0);
ListNode* p1=l1,*p2=l2,*res=myHead;
while(p1&&p2){
if(p1->val<=p2->val){
res->next=p1;
p1=p1->next;
}
else{
res->next=p2;
p2=p2->next;
}
res=res->next;
}
while(p1){
res->next=p1;
p1=p1->next;
res=res->next;
}
while(p2){
res->next=p2;
p2=p2->next;
res=res->next;
}
return myHead->next;
}
};
十一、链表与二叉树
剑指 Offer 36. 二叉搜索树与双向链表（中等难度）
426. 将二叉搜索树转化为排序的双向链表（中等难度）
class Solution {
private:
Node* pre=NULL; // 当前访问节点的前一个节点
Node* head=NULL;// 双向循环链表的头结点
public:
Node* treeToDoublyList(Node* root) {
if(root==NULL) return NULL;
// 采用中序遍历的方式遍历二叉搜索树，修改为双向链表
dfs(root);
// 修改为循环链表
head->left = pre;//头结点指向尾结点
pre->right = head;//尾结点指向头结点
return head;
}
// 中序遍历
void dfs(Node* cur){
// 终止条件
if(cur==NULL) return;
// 递归左节点
dfs(cur->left);
// 处理节点head,pre,cur
if(pre) pre->right=cur;// 如果pre不为空，说明双向链表上已经有节点，其指向当前节点
else head=cur;// 如果pre为空，说明双向链表没有节点，设置头结点
cur->left=pre;// 当前节点指向上一个
pre=cur;// 更新上一个节点
// 递归右节点
dfs(cur->right);
}
};
109. 有序链表转换二叉搜索树（中等难度）
class Solution {
public:
// 在[left,right)获取中间节点
ListNode* getMid(ListNode* left, ListNode* right) {
ListNode* fast = left;
ListNode* slow = left;
while (fast != right && fast->next != right) {
fast = fast->next->next;// 前进2步
slow = slow->next;// 前进1步
}
return slow;
}
// 在[left,right)中序遍历构建二叉搜索树
TreeNode* buildTree(ListNode* left, ListNode* right) {
if (left == right) return nullptr;
// 构建中间节点
ListNode* mid = getMid(left, right);// 获取中间节点
TreeNode* root = new TreeNode(mid->val);//构建根节点
// 递归左右节点
root->left = buildTree(left, mid);
root->right = buildTree(mid->next, right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
return buildTree(head, nullptr);
}
};
114. 二叉树展开为链表（中等难度）
class Solution {
public:
vector<TreeNode*> arr;
void flatten(TreeNode* root) {
dfs(root);
for(int i=1;i<arr.size();++i){
arr[i-1]->right=arr[i];
arr[i-1]->left=nullptr;
arr[i]->left=nullptr;
}
}
void dfs(TreeNode* root){
if(root==nullptr) return;
arr.push_back(root);
dfs(root->left);
dfs(root->right);
}
};
附录
1、单链表的C++实现
#include<iostream>
using namespace std;
/*单链表的实现*/
class SingleList{
private:
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) {}
};
ListNode * head;//头结点,头结点可以直接赋值，其他节点必须在上一个节点处添加
public:
SingleList():head(nullptr){}
/**增加**/
void push_front(int value){
ListNode* newNode= new ListNode(value);
newNode->next=head;
head=newNode;
}
void push_back(int value){
ListNode * newNode=new ListNode(value);
// 如果链表为空添加为头结点
if(head==nullptr) {
head=newNode;
return;
}
// 如果链表不为空添加到链表末尾
else{
// 遍历找到链表的最后一个节点，注意不能是while(p),因为链表节点的添加必须在上一个节点操作
ListNode *p=head;
while(p->next){
p=p->next;
}
p->next=newNode;
}
}
void insert(int index,int value){
if(index<0) return;
if(index==0) push_front(value);
//找到第index个元素
int i=0;
ListNode* p=head;
while(p&&i<index){
i++;
p=p->next;
}
if(p==nullptr) return;
//在第index元素后添加新元素
ListNode* newNode=new ListNode(value);
newNode->next=p->next;
p->next=newNode;
}
/**删除**/
void pop_front(){
if(head!=nullptr){
ListNode* del = head;
head=head->next;
delete del;
}
}
void pop_back(){
this->erase(this->size()-1);
}
// 删除第index个元素
void erase(int index){
if(index<0) return;
if(index==0) pop_front();
else{
//尝试找到第index-1个元素,删除其p->next
ListNode *p=head;
int i=0;
while (p&&i<index-1)
{
p=p->next;
i++;
}
//没有找到，可能是index超出size
if(p==nullptr)return;
//如果找到了且p->next不为空
if(p->next){
ListNode * del=p->next;
p->next=del->next;
delete del;
}
}
}
/**查找**/
int front(){
if(head!=nullptr) return head->val;
return -1;
}
int get(int index){
if(index<0) return -1;
if(index==0) return front();
// 遍历找到第index元素，访问其p->val
int i=0;
ListNode* p=head;
while(p&&i<index){
p=p->next;
i++;
}
// 如果没有找到
if(p==nullptr) return -1;
return p->val;
}
int back(){
return this->get(this->size()-1);
}
int size(){
int len=1;
ListNode* p=head;
if(p==nullptr) return 0;
while(p->next){
len++;
p=p->next;
}
return len;
}
void show(string name=""){
cout<<name;
for(ListNode* p=head;p!=nullptr;p=p->next){
cout<<p->val<<" ";
}
cout<<endl;
}
};
int main()
{
SingleList* lst=new SingleList();
lst->push_back(1);
lst->push_back(2);
lst->push_back(3);
lst->push_front(0);
lst->insert(2,4);
lst->show("插入后:");
cout<<"get:"<<lst->get(1)<<endl;
lst->pop_front();
lst->erase(1);
lst->pop_back();
lst->pop_back();
lst->pop_back();
cout<<"len:"<<lst->size()<<endl;
lst->show("删除后:");
system("pause");
return 0;
}
2、双链表的C++实现
#include<iostream>
using namespace std;
/*双链表的实现*/
class DoubleList{
private:
struct ListNode {
int val;
ListNode *next,*prev;
ListNode() : val(0), next(nullptr),prev(nullptr) {}
ListNode(int x) : val(x), next(nullptr),prev(nullptr) {}
ListNode(int x, ListNode *next,ListNode *prev) : val(x), next(next),prev(prev) {}
};
ListNode * head,*tail;//头结点指向链表第一个元素；尾结点指向最后一个元素
public:
DoubleList():head(nullptr),tail(nullptr){}
/**增加**/
void push_front(int value){
ListNode * newNode=new ListNode(value);
if(head==nullptr){
head=newNode;
tail=head;
}
else{
newNode->next=head;
head->prev=newNode;
head=newNode;
}
}
void push_back(int value){
ListNode * newNode=new ListNode(value);
// 如果尾结点为空添加为尾结点和头结点
if(tail==nullptr) {
tail=newNode;
head=tail;
return;
}
// 如果尾结点不为空添加到尾结点尾部
else{
// 遍历找到链表的最后一个节点，注意不能是while(p),因为链表节点的添加必须在上一个节点操作
newNode->prev=tail;
tail->next=newNode;
tail=newNode;
}
}
// 插入第index个元素
void insert(int index,int value){
if(index<0) return;
if(index==0) push_front(value);
if(index==size()-1) push_back(value);
// 找到第index个元素
int i=0;
ListNode* p=head;
while(p&&i<index){
i++;
p=p->next;
}
if(p==nullptr) return;
// 在index个元素后添加新元素
ListNode* newNode=new ListNode(value);
newNode->next=p->next;
p->next->prev=newNode;
newNode->prev=p;
p->next=newNode;
}
/**删除**/
void pop_front(){
if(head!=nullptr){
ListNode* del = head;
head=head->next;
if(head) head->prev=nullptr; // 如果链表存在2个以上元素
else tail=nullptr;//如果链表只有一个元素
delete del;
}
}
void pop_back(){
if(tail!=nullptr){
ListNode * del= tail;
tail=tail->prev;
if(tail) tail->next=nullptr;
else head=nullptr;
delete del;
}
}
// 删除第index个元素
void erase(int index){
if(index<0) return;
if(index==0) pop_front();
if(index==size()-1) pop_back();
else{
//尝试找到第index个元素,删除其p->next和p->prev
ListNode *cur=head;
int i=0;
while (cur&&i<index)
{
cur=cur->next;
i++;
}
//没有找到，可能是index超出size
if(cur==nullptr)return;
//如果找到了且p->next不为空
ListNode * del=cur;
ListNode *p=cur->prev;
p->next=cur->next;
if(cur->next){
cur->next->prev=p;
}
delete del;
}
}
/**查找**/
int front(){
if(head!=nullptr) return head->val;
return -1;
}
int back(){
if(tail!=nullptr) return tail->val;
return -1;
}
int get(int index){
if(index<0) return -1;
if(index==0) return front();
if(index==size()-1) return back();
// 遍历找到第index元素，访问其p->val
int i=0;
ListNode* p=head;
while(p&&i<index){
p=p->next;
i++;
}
// 如果没有找到
if(p==nullptr) return -1;
return p->val;
}
int size(){
int len=1;
ListNode* p=head;
if(p==nullptr) return 0;
while(p->next){
len++;
p=p->next;
}
return len;
}
void show(string name=""){
cout<<name;
for(ListNode* p=head;p!=nullptr;p=p->next){
cout<<p->val<<" ";
}
cout<<endl;
}
};
int main()
{
DoubleList* lst=new DoubleList();
lst->push_back(1);
lst->push_back(2);
lst->push_back(3);
lst->push_front(0);
lst->insert(3,4);
lst->show("插入后:");
cout<<"get:"<<lst->get(2)<<endl;
lst->pop_front();
lst->erase(2);
lst->pop_back();
// lst->pop_back();
// lst->pop_back();
cout<<"len:"<<lst->size()<<endl;
lst->show("删除后:");
system("pause");
return 0;
}