一、链表的回文判断

解法一:数组反转法

• 将链表值存入数组中
• 创建另一个数组，存储反转数据
• 同时遍历原数组与反转数组，只要有一个元素不同就不是回文结构

class Solution {
public:/*** * @param head ListNode类 the head* @return bool布尔型*/bool isPail(ListNode* head) {// write code herevector<int>v1,v2;;while(head)//存值{v1.push_back(head->val);head=head->next;}v2=v1;reverse(v2.begin(),v2.end());//创建另一个逆序数组for(int i=0;i<v1.size();i++){if(v1[i]!=v2[i])//有一个不相同就不为回文return false;}return true;}
};

时间复杂度:O(n),遍历链表
空间复杂度:O(n),开辟额外辅助数组

解法二

• 将链表数据存入数组
• 使用下标访问，对应头尾比较
• 如果有一个不一样就不是回文结构

class Solution {
public:/*** * @param head ListNode类 the head* @return bool布尔型*/bool isPail(ListNode* head) {// write code herevector<int>v;while(head){v.push_back(head->val);head=head->next;}int len=v.size();for(int i=0;i<len/2;i++)//只利用一个数组从两段比较判断{if(v[i]!=v[len-i-1])return false;}return true;}
};

时间复杂度:O(n),遍历链表
空间复杂度:O(n),开辟额外辅助数组

解法三:反转链表(推荐)

• 求出链表长度
• 长度除2取得链表中点位置
• 从中点位置对后半段链表反转
• 从链表头尾遍历，经反转可以从尾部遍历至中点
• 比较元素是否相等

class Solution {
public:/*** * @param head ListNode类 the head* @return bool布尔型*/ListNode*reverse(ListNode*head)//反转链表{ListNode*newhead=NULL;while(head){ListNode*tmp=head->next;head->next=newhead;newhead=head;head=tmp;}return newhead;}bool isPail(ListNode* head) {// write code hereListNode*cur=head;int count=0;while(cur)//取得节点数{cur=cur->next;count++;}cur=head;for(int i=0;i<count/2;i++)//取得中间节点cur=cur->next;cur=reverse(cur);//反转后半段链表while(cur){if(cur->val!=head->val)//比较return false;cur=cur->next;head=head->next;}return true;}
};

时间复杂度:O(n),其中n为链表的长度
空间复杂度:O(1)

解法四:双指针找中点(推荐)

• 慢指针每次走一个节点，快指针走两个，快指针到尾部时，慢指针到中点
• 其余操作和解法三一样

class Solution {
public:/*** * @param head ListNode类 the head* @return bool布尔型*/ListNode*reverse(ListNode*head)//反转{ListNode*newhead=NULL;while(head){ListNode*tmp=head->next;head->next=newhead;newhead=head;head=tmp;}return newhead;}bool isPail(ListNode* head) {// write code hereListNode*fast=head,*slow=head;while(fast&&fast->next)//双指针找中点{fast=fast->next->next;slow=slow->next;}slow=reverse(slow);//反转后半部分while(slow){if(slow->val!=head->val)//比较return false;slow=slow->next;head=head->next;}return true;}
};

时间复杂度:O(n),其中n为链表的长度
空间复杂度:O(1)

解法五:栈

• 将链表元素入栈
• 弹出元素值和链表顺序遍历比较

class Solution {
public:/*** * @param head ListNode类 the head* @return bool布尔型*/bool isPail(ListNode* head) {// write code herestack<int>s;ListNode*cur=head;while(cur)//存值{s.push(cur->val);cur=cur->next;}while(head){if(head->val!=s.top())//比较return false;head=head->next;s.pop();}return true;}
};

• 时间复杂度:O(n),遍历链表
  空间复杂度:O(n),开辟额外辅助栈

二、链表的奇偶重排

解法:双指针(推荐)

• 判断链表为NULL的情况，为空直接返回NULL
• 使用odd和even俩个指针分别遍历奇数和偶数指针，给偶数链表设置一个头
• 每次遍历两个链表，even在后，因此用even作为循环结束的判断依据
• 将偶数头节点连接在奇数尾节点后，返回链表头部

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* oddEvenList(ListNode* head) {// write code hereif(head==NULL)return head;ListNode*odd=head;ListNode*even=head->next;ListNode*evenhead=even;//偶数链表头while(even&&even->next){odd->next=even->next;//偶数下一位是奇数odd=odd->next;even->next=odd->next;//奇数下一位是偶数even=even->next;}odd->next=evenhead;//连接奇偶return head;}
};

时间复杂度:O(n),遍历依次链表
空间复杂度:O(1)

三、删除链表中的重复元素

题目一:

解法:遍历删除(推荐)

• 先判断是否为空
• 遍历链表，当前节点值与下一节点值相同则跳过此节点，连接下一节点(本题链表节点值升序排列)
• 不同继续向后遍历
• 要检查连续两节点是否为空

class Solution {
public:/*** * @param head ListNode类 * @return ListNode类*/ListNode* deleteDuplicates(ListNode* head) {// write code hereif(head==NULL)return head;ListNode*cur=head;while(cur&&cur->next){if(cur->val==cur->next->val)//连续两值比较，相同跳过{ListNode*tmp=cur->next;cur->next=cur->next->next;delete tmp;}else//不同继续遍历cur=cur->next;}return head;}
};

时间复杂度:O(n),n为链表长度
空间复杂度:O(1)

题目二:

解法一:直接比较删除(推荐)

• 设置虚拟链表表头,便于可能的链表头的删除
• 遍历链表，每次比较相邻节点，如果相同，则创建循环将这一段所有相同的都遍历跳过去
• 上一步的一连串相同节点的前节点直接连接到后续第一个不同值得节点

class Solution {
public:/*** * @param head ListNode类 * @return ListNode类*/ListNode* deleteDuplicates(ListNode* head) {// write code hereif(head==NULL)return head;ListNode*dummy=new ListNode(-1);//设置虚拟头dummy->next=head;ListNode*cur=dummy;while(cur->next&&cur->next->next)//连续两个不为空{if(cur->next->val==cur->next->next->val){int tmp=cur->next->val;while(cur->next&&cur->next->val==tmp)//值相同的都掠过{cur->next=cur->next->next;}}elsecur=cur->next;}return dummy->next;}
};

时间复杂度:O(n),n为链表长度
空间复杂度:O(1)

解法二:哈希表

• 遍历链表记录各解点值出现次数
• 设置虚拟头
• 再次遍历链表，只保留哈希计数为一的节点

class Solution {
public:/*** * @param head ListNode类 * @return ListNode类*/ListNode* deleteDuplicates(ListNode* head) {// write code hereif(head==NULL)return head;unordered_map<int, int>m;ListNode*cur=head;while(cur){m[cur->val]++;cur=cur->next;}ListNode*dummy=new ListNode(-1);dummy->next=head;cur=dummy;while(cur->next){if(m[cur->next->val]!=1)//不为1即重复cur->next=cur->next->next;//覆盖elsecur=cur->next;}return dummy->next;}
};

时间复杂度:O(n),遍历链表，节点数n
空间复杂度:O(n),最坏情况，n个节点值都不同，哈希长度为n

解法三:递归

在解法一的基础上用递归代替循环

class Solution {
public:/*** * @param head ListNode类 * @return ListNode类*/ListNode* deleteDuplicates(ListNode* head) {// write code hereif(head==NULL||head->next==NULL)return head;ListNode*cur=head->next;if(head->val==cur->val){while(cur&&head->val==cur->val)cur=cur->next;head=deleteDuplicates(cur);//相当于用递归代替了外层循环}elsehead->next=deleteDuplicates(cur);//如果值不同，切换下一节点进行递归判断return head;}
};

时间复杂度:O(n),遍历链表，节点数n
空间复杂度:O(n),最坏情况递归栈深度为n

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！