北京网站优化校学费,开个跨境电商要多少钱,oa系统品牌,微分销系统哪家比较好目录 前言
1.反转一个单链表。
2. 给定一个带有头结点 head 的非空单链表#xff0c;返回链表的中间结点。
3.链表的回文结构。 4.链表带环问题#xff08;*****#xff09;
4.1是否带环
4.2 入环的节点
5.随机链表的复制#xff08;链表的深拷贝#xff09; 前言…目录 前言
1.反转一个单链表。
2. 给定一个带有头结点 head 的非空单链表返回链表的中间结点。
3.链表的回文结构。 4.链表带环问题*****
4.1是否带环
4.2 入环的节点
5.随机链表的复制链表的深拷贝 前言 前面我们学习了链表现在我们来手撕几道经典链表OJ题目吧 1.反转一个单链表。 题目链接206. 反转链表 - 力扣LeetCode 题解 在这一题我们定义了三个指针变量首先让prev指向NULLprev的作用是保存cur的前面的一个节点next是保存cur后面的节点。 每一次循环迭代都让cur指向前面的节点也就是指向prev 再让prev去到cur的位置cur去到next位置最后再让next去到cur-next的位置这样就完成了一次循环迭代。直到cur为NULL struct ListNode* reverseList(struct ListNode* head) {struct ListNode*prev NULL;struct ListNode*cur head;struct ListNode*next head;while(cur){next cur-next;cur-next prev;prev cur;cur next;}return prev;
} 这样就通过了 2. 给定一个带有头结点 head 的非空单链表返回链表的中间结点。 题目链接876. 链表的中间结点 - 力扣LeetCode 题解 这题思想其实非常简单既然让返回中间节点那么我们就定义两个指针fast和slow让fast走两步slow走一步这样fast走完全程之后slow就只走了一半。 需要注意的是节点总数为奇数时fast走到最后一个节点就结束而节点总数为偶数时fast节点就要走到NULL。因此结束条件就要写成fastfast-next。 struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow head,*fast head;while(fastfast-next){slow slow-next;fast fast-next-next;}return slow;
} 3.链表的回文结构。 题目链接链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 题解 这一题看似复杂实际不难。我们只需要找到中间节点然后从中间节点反转链表 再分别从两个头开始遍历若每个节点都相等则为回文结构。 如果是奇数个两条链表节点数量会不会不想等呢 不会因为A链表的最后一个并没有与B链表的最后一个节点断开所以两链表有一个 公共节点因此在奇数个节点下两链表节点个数也相同结束条件显而易见为headrhead。 class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) {//反转链表struct ListNode*prv NULL;struct ListNode*cur head;struct ListNode*n head;while(n){n cur-next;cur-next prv;prv cur;cur n;}return prv;
}
struct ListNode* middleNode(struct ListNode* head){//找中间节点struct ListNode* slow head,*fast head;while(fastfast-next){slow slow-next;fast fast-next-next;}return slow;
}bool chkPalindrome(ListNode* A) {ListNode* mid middleNode(A);ListNode*rhead reverseList(mid);while(Arhead){if(A-val!rhead-val)return false;AA-next;rheadrhead-next;}return true;}
}; 4.链表带环问题***** 链表带环问题是链表中非常重要的一类问题在企业面试中也会经常遇到。此类问题有两种第一种是判断链表是否带环第二种是判断链表开始入环的节点是哪个。 4.1是否带环 题目链接141. 环形链表 - 力扣LeetCode 题解我们不禁思索该如何判断链表是否带环呢 在这里我们可以定义两个指针fast和slow让fast先走如果到最后还能与slow相遇那就证明该链表是带环的。在此就引出了一个问题fast要比slow快多少 1.slow一次走一步fast一次走两步一定会相遇吗 答案是一定会相遇因为fast和slow的距离每次都缩减1到最后一定会减到0。 2.slow一次走一步fast一次走三步一定会相遇吗 答案是不一定如果N为偶数fast和slow的距离每次都缩减2最后一定会减到0。如果为奇数最后会减到-1这样就又开始新一轮的追击了而且永远不会相遇。 3.slow一次走n步fast一次走m步一定会相遇吗mn1 最后我们得到2L n*C-N最后一定得到的是一个奇数所以最后一定能追上。 bool hasCycle(struct ListNode *head) {struct ListNode* fast head,*slow head;while(fastfast-next){fast fast-next-next;slow slow -next;if(fast slow)return fast;}return NULL;
} 4.2 入环的节点 题目链接142. 环形链表 II - 力扣LeetCode 、 题解这一题与上一题是不一样的这一题是要找到入环的节点从哪个节点开始入环这题难度相较于上一题显然是上升了。 假设fast和slow在meet点相遇那么slow就走了LX的距离fast就走了LXn*C的距离最后由图上等式可得Ln*C-X那也就是说如果相同速度的指针一个从相遇点开始走另一个从入口点开始走他们到入口与点的距离是一样的所以一定会在入口点相遇。 因此本题思路就出来了1.找到相遇点 2.让相同速度的指针一个从相遇点开始走另一个从入口点开始走。最终就一定会相遇。 struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow head,*fast head;while(fastfast-next){slow slow-next;fast fast-next-next;if(slow fast){struct ListNode* meet slow;while(head!meet){head head-next;meet meet-next;}return meet;}}return NULL;
} 5.随机链表的复制链表的深拷贝 题目链接138. 随机链表的复制 - 力扣LeetCode 题解链表的深拷贝是链表中较难的问题但如果把思路理清问题也就迎刃而解了。 我们的第一思路可能就是将每个节点的信息先拷贝下来然后我们来处理random的指向的时候可能就是用嵌套循环将每个节点的random进行比较来确定指向这样一来就造成时间复杂度到达O(N^2)了这就不符合题目要求了。 那么我这里就提供一种可行的思路 1.拷贝的节点都插入在原来节点的后面如图 2.处理random的指向 我们可以清楚的看到原节点的下一个节点就是我们所拷贝的节点那么让本来指向原节点random指向原节点的下一个是不是就可以让拷贝节点的random完成正确的指向这就解决了然random指向的问题了。如图我们已经得到所有的拷贝节点了。 3.copy的节点一个一个的解下来尾插就可以得到我们想要的深拷贝出来的链表了。 完整代码 truct Node* copyRandomList(struct Node* head) {struct Node* cur head;while(cur){struct Node*copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;copy-next cur-next;cur-next copy;curcur-next-next;}cur head;while(cur){struct Node*copy cur-next;if(cur-random NULL)copy-random NULL;elsecopy-random cur-random-next;cur cur-next-next; }struct Node* newhead NULL,*failNULL;cur head;while(cur){struct Node*copy cur-next;struct Node*next copy-next;if(newheadNULL){newhead fail copy;}else{fail-next copy;failfail-next;}cur-next next;cur next;}return newhead;
} 这里都是链表比较经典的题目希望对你有所帮助
