编号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; }
