html做网站实战教程,国际阿里网站首页建设,网络工程师考试内容,wap网站域名Leetcode Leetcode -86.分隔链表Leetcode -92.反转链表Ⅱ Leetcode -86.分隔链表
题目#xff1a;给你一个链表的头节点 head 和一个特定值 x #xff0c;请你对链表进行分隔#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每… Leetcode Leetcode -86.分隔链表Leetcode -92.反转链表Ⅱ Leetcode -86.分隔链表
题目给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。
示例 1 输入head [1, 4, 3, 2, 5, 2], x 3 输出[1, 2, 2, 4, 3, 5]
示例 2 输入head [2, 1], x 2 输出[1, 2]
我们的思路是遍历链表的每个元素如果比x小则拿下来放到一个small的结构体指针中否则放到一个large的指针中最后判断small是否为空如果为空则说明链表中的元素全都是比x大或等于x否则链表中的元素有比x大或等于也有比x小的这时候将small的尾部接到large上即可 struct ListNode* partition(struct ListNode* head, int x){//small放比x小的值//large放大于等于x的值//smalltail和largetail分别是它们的尾struct ListNode* large NULL, * small NULL;struct ListNode* largetail NULL, * smalltail NULL;//从头开始遍历到空结束while (head){//head的val比x小放到smallif (head-val x){//当small为空即没有值的时候small和smalltail都更新为当前的head//head迭代往后走尾的next置空if (small NULL){small smalltail head;head head-next;smalltail-next NULL;}//否则更新尾并迭代head即可else{smalltail-next head;head head-next;smalltail smalltail-next;smalltail-next NULL;}}//当head的val比x大或等于x与上面类似else{if (large NULL){large largetail head;head head-next;largetail-next NULL;}else{largetail-next head;head head-next;largetail largetail-next;largetail-next NULL;}}}//如果链表中的值有大有小即small这个链表不为空就将small尾部的next接到large然后再返回smallif (small)smalltail-next large;//这种情况则是链表中的值全都大于或等于x直接返回large即可elsereturn large;return small;}Leetcode -92.反转链表Ⅱ
题目给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。 请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。
示例 1 输入head [1, 2, 3, 4, 5], left 2, right 4 输出[1, 4, 3, 2, 5]
示例 2 输入head [5], left 1, right 1 输出[5]
我们的思路是使用leftcur和rightcur指针走到链表中left位置和right位置反转left位置到right位置即可当left为1即在头节点的位置时最终只需要返回反转后的链表当left不在头节点的位置我们用一个指针cur记录leftcur的前一个位置我们只需要将cur-next 接到反转后的链表并返回头节点即可
当left 1right 3 反转后整理的链表返回prev即可即返回反转后的链表 当left不为1left 2right 3 在函数中反转后的链表如下两个图所以需要将原链表中cur-next接到反转后的链表中再返回head 代码以及注释 struct ListNode* Reverse(struct ListNode* prev, struct ListNode* dest){struct ListNode* curr prev-next;prev-next dest-next;while (prev ! dest){struct ListNode* next curr-next;curr-next prev;prev curr;curr next;}return prev;}struct ListNode* reverseBetween(struct ListNode* head, int left, int right){//当左下标和右下标相同不需要反转返回headif (left right)return head;struct ListNode* cur head;struct ListNode* leftcur head, * rightcur head;//leftcur走到链表中left的位置while (--left){leftcur leftcur-next;}//rightcur走到链表中right的位置while (--right){rightcur rightcur-next;}//cur从头遍历当cur等于leftcur或者cur-next等于leftcur时停下while (cur ! leftcur cur-next ! leftcur){cur cur-next;}//cur-next等于leftcur反转leftcur到rightcur长度的链表//并且将cur的next接到反转后的链表去//返回头节点if (cur ! leftcur){cur-next Reverse(leftcur, rightcur);return head;}//cur等于leftcur即cur leftcur head//就反转leftcur到rightcur长度的链表返回反转后的链表即可else{return Reverse(leftcur, rightcur);}}
