刷爆leetcode第四期 0011~0015

刷爆leetcode第四期

编号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;
 * };
 */structListNode*partition(structListNode* head,int x){if(head==NULL){returnNULL;}structListNode* lesshead =NULL;structListNode* betterhead =NULL;structListNode* lesstail =NULL;structListNode* bettertail =NULL;structListNode* 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;}

解法二

除了上面那一种解法之外我们还可以使用一个新的解法

利用我们学到的基础知识 头插 尾插

如果这个数小于我们规定的值就头插到新链表

如果这个数大于等于我们规定的值就尾插到新链表

画图表示如下

代码表示如下

structListNode*partition(structListNode* head,int x){if(head ==NULL){returnNULL;}structListNode* newhead =NULL;structListNode* newtail =NULL;structListNode* pos = head;structListNode* 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(structListNode* head){if(head==NULL){return true;}int* num_val =(int*)malloc(sizeof(int)*100001);int count =0;structListNode* 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）

我们首先写两个函数

一个寻找中间节点

一个逆序单链表

代码表示如下

structListNode*Findhalf(structListNode* head){assert(head);structListNode* slow=head;structListNode* fast=head;while((fast!=NULL)&&(fast->next!=NULL)){
        slow=slow->next;
        fast=fast->next->next;}return slow;}structListNode*reversehalf(structListNode* half){// 这里其实补判断空指针也可以 不过大家尽量养成一个好习惯 if(half ==NULL){returnNULL;}structListNode* prev =NULL;structListNode* pos =half;structListNode* next =half;while(pos){
        next=next->next;
        pos->next = prev;
        prev = pos;
        pos =next;}return prev;}

bool isPalindrome(structListNode* head){if(head==NULL){return true;}structListNode* half =NULL;structListNode* halfstart =NULL;// 找到中间节点 
    half =Findhalf(head);// 翻转中间节点 
    halfstart =reversehalf(half);// 比较两个链表 structListNode* p1 =head;structListNode* p2 =halfstart;while(p1&&p2){if(p1->val!=p2->val){return false;}
        p1=p1->next;
        p2=p2->next;}return true;}

编号0013 双链表相交节点

输入两个链表，找出它们的第一个公共节点。

这道题目也很简单

使用双指针法就可以轻松解决

如下图

如果它们有交点

那么它们就会在交点处相遇

如果它们没有交点

那么它们就会在空指针处相遇

代码表示如下

structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){if(headA==NULL){returnNULL;}if(headB==NULL){returnNULL;}structListNode*l1 =headA;structListNode*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(structListNode*head){if(head==NULL|| head->next ==NULL){returnNULL;}structListNode* fast = head->next;structListNode* 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指针从遇见的点开始走

它们会在环的起点相遇

代码表示如下

structListNode*detectCycle(structListNode*head){if(head==NULL|| head->next==NULL){returnNULL;}structListNode*slow =head;structListNode*fast =head;structListNode*cur =head;structListNode*pos  =NULL;structListNode*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;}}returnNULL;}