刷爆leetcode第四期 0011~0015
刷爆leetcode第四期
- 编号0011 分割链表
- 解法一
- 解法二
- 编号0012 回文链表
- 解法一
- 解法二
- 编号0013 双链表相交节点
- 编号0014 环形链表
- 编号0015 环形链表二
编号0011 分割链表
解法一
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-list-lcci
我们来看图
其实这个题目解释起来也简单
我们要将整个数组所有小于x的值放在x的左边
所有大于x的值放在x的右边
解决这个问题我们可以设计两个新链表
然后遍历链表 如果遍历到的元素小于x我们就将它放到创造的第一个链表当中
如果遍历到的元素大于x我们就就将它放到创造的第二个链表当中
我们这里提交代码
发现最后这里出错了
检查下 发现我们忽略了两种特殊情况
如果都大于或者都小于呢
所以我们补上后面的代码
加上后面这段代码之后就能过了
代码完整表示如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x)
{
if(head==NULL)
{
return NULL;
}
struct ListNode* lesshead = NULL;
struct ListNode* betterhead = NULL;
struct ListNode* lesstail = NULL;
struct ListNode* bettertail = NULL;
struct ListNode* pos = head;
// pos节点指向空的时候就不进去了 注意结束条件
while(pos)
{
if(pos->val<x)
{
if(lesshead==NULL)
{
lesshead=lesstail=pos;
}
else
{
// 尾插数据 注意这里其实lesstail=pos也一样
lesstail->next=pos;
lesstail=lesstail->next;
}
}
else
{
if(betterhead==NULL)
{
betterhead=bettertail=pos;
}
else
{
//写一种不同的写法 方便大家理解
bettertail->next = pos;
bettertail = pos;
}
}
pos=pos->next;
}
if(lesstail==NULL)
{
return betterhead;
}
if(bettertail==NULL)
{
return lesshead;
}
lesstail->next = betterhead;
bettertail->next = NULL;
return lesshead;
}
解法二
除了上面那一种解法之外我们还可以使用一个新的解法
利用我们学到的基础知识 头插 尾插
如果这个数小于我们规定的值就头插到新链表
如果这个数大于等于我们规定的值就尾插到新链表
画图表示如下
代码表示如下
struct ListNode* partition(struct ListNode* head, int x)
{
if (head == NULL)
{
return NULL;
}
struct ListNode* newhead = NULL;
struct ListNode* newtail = NULL;
struct ListNode* pos = head;
struct ListNode* next = head;
while (next)
{
next = next->next;
if (pos->val < x)
{
pos->next = newhead;
newhead = pos;
if (newtail==NULL)
{
newtail = newhead;
}
}
else
{
if (newhead == NULL)
{
newhead = head;
newtail = head;
newtail->next = NULL;
}
else
{
newtail->next = pos;
pos->next = NULL;
newtail = pos;
}
}
pos = next;
}
return newhead;
}
这里要注意的是 在既要头插又要尾插的问题中
第一次赋值的时候 一定要把第一个数组的next赋值给空指针
编号0012 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
解法一
这里我们有很多种解法
我们先给一种时间复杂度O（N）空间复杂度O（N）的 数组法
还是直接上图
上代码
bool isPalindrome(struct ListNode* head)
{
if(head==NULL)
{
return true;
}
int* num_val = (int *)malloc(sizeof(int)*100001);
int count =0;
struct ListNode* pos =head;
while(pos)
{
num_val[count++]=pos->val;
pos = pos->next;
}
int left =0;
int right = count-1;
while(left<right)
{
if(num_val[left]!=num_val[right])
{
return false;
}
left++;
right--;
}
return true;
}
很简单的解法 也不需要多讲什么了
只有一点要注意的是
空链表是回文链表
解法二
这个解法就比较有难度了
但是它能够将我们的空间复杂度降低至O（1）
我们首先写两个函数
一个寻找中间节点
一个逆序单链表
代码表示如下
struct ListNode* Findhalf(struct ListNode* head)
{
assert(head);
struct ListNode* slow=head;
struct ListNode* fast=head;
while((fast!=NULL)&&(fast->next!=NULL))
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
struct ListNode* reversehalf(struct ListNode* half)
{
// 这里其实补判断空指针也可以 不过大家尽量养成一个好习惯
if(half == NULL)
{
return NULL;
}
struct ListNode* prev =NULL;
struct ListNode* pos =half;
struct ListNode* next =half;
while(pos)
{
next=next->next;
pos->next = prev;
prev = pos;
pos =next;
}
return prev;
}
bool isPalindrome(struct ListNode* head)
{
if(head==NULL)
{
return true;
}
struct ListNode* half =NULL;
struct ListNode* halfstart =NULL;
// 找到中间节点
half = Findhalf(head);
// 翻转中间节点
halfstart = reversehalf(half);
// 比较两个链表
struct ListNode* p1 =head;
struct ListNode* p2 =halfstart;
while(p1&&p2)
{
if(p1->val!=p2->val)
{
return false;
}
p1=p1->next;
p2=p2->next;
}
return true;
}
编号0013 双链表相交节点
输入两个链表，找出它们的第一个公共节点。
这道题目也很简单
使用双指针法就可以轻松解决
如下图
如果它们有交点
那么它们就会在交点处相遇
如果它们没有交点
那么它们就会在空指针处相遇
代码表示如下
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
if(headA==NULL)
{
return NULL;
}
if(headB==NULL)
{
return NULL;
}
struct ListNode *l1 =headA;
struct ListNode *l2 =headB;
while(l1!=l2)
{
l1=l1==NULL?headB:l1->next;
l2=l2==NULL?headA:l2->next;
}
return l2;
}
编号0014 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle
还是先上图
我们先来看有环的情况
这个时候实际上fast和slow会在里面陷入死循环
我们把这个图再抽象下
实际上就是一个这样子的图形
大家有没有表示眼熟？
这不就是我们的操场吗
那么我们把问题变一下
两个人跑步 一个跑的比较快 一个跑的比较慢
如果在一个直线的操场上它们会相遇嘛？
显然不会
但是如果在一个环形的操场上呢？
那必然会啊
那么我们接着来看
所以说这里就论证了当fast=2 slow=1时
它们在某个节点相遇的必然性
所以这个时候我们就可以上手写代码了
代码表示如下
bool hasCycle(struct ListNode *head)
{
if(head==NULL || head->next == NULL)
{
return NULL;
}
struct ListNode * fast = head->next;
struct ListNode * slow = head;
while(fast!=NULL && fast->next!=NULL)
{
if(slow==fast)
{
return true;
}
else
{
slow = slow->next;
fast = fast->next->next;
}
}
return false;
}
编号0015 环形链表二
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii
这一题跟上一题一样
这样子就证明了
一个slow指针从起点开始走
一个slow指针从遇见的点开始走
它们会在环的起点相遇
代码表示如下
struct ListNode *detectCycle(struct ListNode *head)
{
if(head==NULL || head->next==NULL)
{
return NULL;
}
struct ListNode *slow =head;
struct ListNode *fast =head;
struct ListNode *cur =head;
struct ListNode *pos =NULL;
struct ListNode *meet =NULL;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
{
meet = fast;
while(meet!=cur)
{
cur=cur->next;
meet=meet->next;
}
pos = meet;
return pos;
}
}
return NULL;
}