佛山正规的免费建站,wordpress导航仿制,奉节集团网站建设,wordpress获取文章页id本篇博客介绍#xff1a; 介绍下链表相关的算法题 链表相关算法题 快慢指针回文结构链表将单向链表按某值划分为左边小#xff0c;中间相等#xff0c;右边大的形式复制带随机指针的链表 链表相关的算法题其实都算不上难 我们真正要考虑的是一些边界问题 事实上链表题就是在…本篇博客介绍 介绍下链表相关的算法题 链表相关算法题 快慢指针回文结构链表将单向链表按某值划分为左边小中间相等右边大的形式复制带随机指针的链表 链表相关的算法题其实都算不上难 我们真正要考虑的是一些边界问题 事实上链表题就是在锻炼我们的处理边界能力 其次我们要强调的一点是 在笔试和面试中 我们的解题思路是不同的
在笔试中我们一般追求快速解题 只需要考虑时间复杂度 一般空间复杂度上不会卡你
但是在面试中 我们必须要在保证时间复杂度的情况下考虑空间复杂度 因为面试官会根据你写出的代码来判断你对于这个问题真正理解多少 有没有达到要求
快慢指针
比如说现在题目要求我们找出一个链表的中点
常规的解法就是 我们数一下链表的长度是多少
数出链表的长度之后除以二 之后使用指针一步步遍历到中点位置即可 快慢指针法解决中点问题 我们可以设计两个指针 快指针和慢指针
慢指针每次走一步
快指针每次走两步
我们可以通过调整快慢指针谁先走来调整中点
当然其中也有一些边界问题 比如说空指针的引用需要注意
lc上原题的连接如下
链表的中间节点
C代码如下
class Solution {
public:ListNode* middleNode(ListNode* head) {if (head - next nullptr){return head;}ListNode* slow head;ListNode* fast head;while(fast fast-next){slow slow-next;fast fast-next-next;} return slow;}
};此外 快慢指针还能解决链表第K个节点之类的问题 思路同上
回文结构链表
正读和反读都相同的字符序列为回文
比如说下面的这一行字符
1 2 3 2 1 这就是一个回文结构
但是如果我们改变下最后节点的值 变成
1 2 3 2 2 这就不是一个回文结构了
判断它是不是一个回文结构我们也有多种做法
如果是在笔试中 我们可以选择最简单的 使用一个栈结构去解
具体解法为
我们首先定义一个栈结构从头开始遍历所有的链表值 将所有的链表值放到栈结构中这样子我们就得到了一个逆序的链表值于是我们只要再次从头开始遍历整个链表 并且与栈中的逆序值做对比即可
题目连接和代码表示如下
回文链表
class Solution {
public:bool isPalindrome(ListNode* head) {if (head-next nullptr){return true;}stackint st;ListNode* cur head;while(cur){st.push(cur-val);cur cur-next;}cur head;while(!st.empty()){if (st.top() cur-val){st.pop();cur cur-next;}else {return false;}}return true;}
};但是上面的解法仅限于笔试中 如果在面试中我们遇到了这个问题肯定是面试官想考查我们空间复杂度为O1的解法
其实思路也很简单
找到链表的左中点 并且指向空翻转整个链表的右半部分以左中点为结束位置设置两个指针 分别从左右开始对比值 如果全部相同 最后返回true 反之返回false最后一定要记得将链表复原
代码表示如下
class Solution {
public:bool isPalindrome(ListNode* head) {if (head-next nullptr){return true;}// 0 设置返回值bool ret true;// 1 找出链表的左中点ListNode* slow head;ListNode* fast head;while(fast-next fast-next-next){fast fast-next-next;slow slow-next;}// 2 设置左右中点ListNode* leftmidpoint slow; ListNode* rightmidpoint slow-next; // 排除掉了一个节点的情况 不可能为空// 3 开始翻转ListNode* n1 leftmidpoint;ListNode* n2 rightmidpoint;ListNode* n3 rightmidpoint-next; // 有可能为空leftmidpoint-next nullptr;while(1){n2 -next n1;n1 n2;n2 n3;if (n3){n3 n3-next;}else {break;}}ListNode* righthead n1;ListNode* cur1 head;ListNode* cur2 righthead;while (cur1 ! nullptr){if (cur1-val cur2-val){cur2 cur2-next;cur1 cur1-next;}else{ret false;break;}}// 4 还原链表 leftmidpoint-next rightmidpoint;n1 righthead;n2 righthead-next;righthead-next nullptr;if (n2 leftmidpoint){return ret;}n3 n2-next;while(1){ n2-next n1;n1 n2;n2 n3;if (n3 leftmidpoint){break;}else {n3 n3-next;}}return ret;;}
};将单向链表按某值划分为左边小中间相等右边大的形式
题目要求如下 链接https://www.nowcoder.com/questionTerminal/04fcabc5d76e428c8100dbd855761778 来源牛客网 给定一个链表再给定一个整数 pivot请将链表调整为左部分都是值小于 pivot 的节点中间部分都是值等于 pivot 的节点 右边部分都是大于 pivot 的节点。 除此之外对调整后的节点顺序没有更多要求。
解题思路上其实没有难点
我们设置六个指针 分别是小头 小尾 等头 等尾 大头 大尾即可之后遍历链表 更新上面的指针最后让这些指针相连有一个难点就是我们要考虑有区域为空的情况
代码表示如下
# include bits/stdc.h
using namespace std;struct list_node{int val;struct list_node * next;
};
#define Node list_node
int pivot;list_node * input_list(void)
{int n, val;list_node * phead new list_node();list_node * cur_pnode phead;scanf(%d%d, n, pivot);for (int i 1; i n; i) {scanf(%d, val);if (i 1) {cur_pnode-val val;cur_pnode-next NULL;}else {list_node * new_pnode new list_node();new_pnode-val val;new_pnode-next NULL;cur_pnode-next new_pnode;cur_pnode new_pnode;}}return phead;
}
void insertHead(Node *head, Node* x) {if(xNULL || headNULL) return;Node* last head-next;head-next x;x -next last;
}list_node * list_partition(list_node * head, int pivot)
{//在下面完成代码if(headNULL || head-next NULL)return head;Node dummy_head;list_node *first head;list_node lt,gt,eq;Node *l lt,*g gt, *e eq;lt.next gt.next eq.next NULL;while(first) {if(first -val pivot) {e -next first,first first-next,e e-next,e-next NULL;}else if(first-val pivot) {g -next first,first first-next, g g-next,g-next NULL;}else {l-next first,l l-next,first first-next, l-next NULL;}}e-next gt.next;l-next eq.next;first lt.next;while(first) {printf(%d , first-val);first first-next;}return lt.next;}int main ()
{list_node * head input_list();list_partition(head, pivot);return 0;
}
复制带随机指针的链表
题目描述可以直接参考leetcode
我这里就不水字数了
复制随机指针的链表
这个题目在我刚刚接触C的时候其实也做过一次 博客连接如下
复制带随机指针的链表
这个题目的难点其实只有一个
如何确定随机指针指向的位置 如果随机指针指向的位置一定是向后的话我们倒是可以使用数步数的方式来实现 可要是随机指针指向的是前面呢 通过遍历去找嘛
这样子时间复杂度直接上N方了 肯定是过不了的
那么我们解决这个难点的思路有两个
使用哈希表 哈希表的KEY值对应原节点 VALUE值对应复制的节点 这样子我们只要找到原来的节点的随机指针 再到哈希表中找对应的VALUE值即可因为随机指针本质上就是指向该链表中的某一个节点 所以说只要我们能够确定该链表中任意一个节点的相对位置 我们就能够找到复制后的随机指针应该指向哪里 于是我们可以选择在原链表的每个节点后面加上一个复制的节点 这样子我们通过原链表的随机指针找到对应的节点后下一个节点就是我们复制节点的随机指针应该指向的节点了
这两种方法的时间复杂度都是O(N) 但是第一种方法的空间复杂度要高一些
所以说我们在面试中要选用第二种方法 在笔试中可以选择第一种方法
代码表示如下
class Solution {
public:Node* copyRandomList(Node* head) {if (head nullptr){return nullptr;}// 1 复制节点到原节点后Node* cur head;Node* NEXT nullptr; // null?while (cur){NEXT cur - next;cur - next new Node(cur-val); cur - next - next NEXT;cur NEXT;}// 2 随机指针开始拷贝 Node* cur2 head-next;cur head;while(cur){cur2 cur-next;if (cur-random){cur2-random cur-random-next;}else {cur2-random nullptr;}cur cur-next-next;}// 3 分离出复制的节点cur2 head-next;cur head;NEXT nullptr;Node* NEXT2 nullptr;head cur2;while(cur){NEXT cur-next-next;if (NEXT nullptr){NEXT2 nullptr;}else {NEXT2 NEXT-next;}cur-next NEXT;cur2-next NEXT2;cur NEXT;cur2 NEXT2;}return head;}
};
