[TOC]
本文主要记录链表的循环、分割、排序的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。
一、循环链表的LeetCode题目
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;
}
};
二、链表分隔的LeetCode题目
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;
}
};
三、链表排序的LeetCode题目
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;
}
};