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小,放到small if (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,然后再返回small if (small) smalltail->next = large; //这种情况则是链表中的值全都大于或等于x,直接返回large即可 else return 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 = 1,right = 3:
反转后整理的链表,返回prev即可,即返回反转后的链表;
当left不为1,left = 2,right = 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) { //当左下标和右下标相同,不需要反转,返回head if (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); } }