好好学习,giao哥给你补🥚
1、移除链表元素
难度等级:⭐
题目链接:移除链表元素
2、链表的中间节点
难度等级:⭐⭐
题目链接:链表的中间节点
3、反转链表
难度等级:⭐⭐⭐
题目链接:反转链表
4、合并两个有序链表
难度等级:⭐⭐⭐⭐
题目链接:合并两个有序链表
5、分割链表
难度等级:⭐⭐⭐⭐⭐
题目链接:分割链表
6、环形链表的约瑟夫问题
难度等级:⭐⭐⭐⭐⭐⭐
题目链接:环形链表的约瑟夫问题
注:难度等级设置只是相对而言,仅供参考
–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
1、移除链表元素
题目链接:移除链表元素
题目:
解题思路: 定义一个新链表,遍历原链表找到不为val的节点,尾插在新链表当中。
解题代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode* newTail,*newHead;
newTail = newHead = NULL;
ListNode* pcur = head;
while(pcur)
{
if(pcur->val != val)
{
if(newHead == NULL)
{
newHead = newTail = pcur;
}
else
{
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = pcur->next;
}
if(newTail)
{
newTail->next = NULL;
}
return newHead;
}
该题为接口性问题,我们只要知道单链表结构体类型,知道如何来解题即可。
代码讲解:
第一步我们需要创建两个结构体指针,分别用来标记新链表的头(newHead)和尾(newTail),对于所传过来的形参head保险起见一般是不能直接改他的值的,所以我们创建结构体变量pcur来代替head进行链表的遍历。
这里先强调一下只要进入while循环,那么就说明原链表不为空链表,之后就可以判定当pcur所指的节点val不等于所给的val时就要进行尾插,同时我们还需要考虑所创建的新链表是否为空,也就是是否已经插入了节点,因为当第一次向新链表插入节点时我们的头指针newHead和尾指针newTail都需要指向该节点,而之后如果继续插入的话只需要移动尾指针newTail即可,所以我们是需要考虑新链表是否为空的情况。
那么如果pcur所指的节点val等于所给的val时我们直接将pcur向前面的节点移动即可(pcur = pcur->next)。
完成上面操作后,要让大家自己写的话可能有人会直接返回头节点的指针就结束了,但这是不对的
我们就拿上面的图为例,val = 6,那么当pcur移动到第7个节点(最后一个节点)的时候我们按照上面所讲的逻辑就会把第7个节点进行删除,但是第6个节点的next里面还存着第7个节点的地址,所以我们还需要把第6个节点的next改成指向NULL,也就是代码中的if(newTail),判断newTail是否为空,因为上面我们也提到过**“只要进入while循环,那么就说明原链表不为空链表”**,那么只要出了while循环就说明pcur已经是空指针了,而如果newTail不为空,就说新链表里面已经“存有”节点了,那么直接newTail->next = NULL就完成将最后节点的指向改为空指针了而当newTail为空的时候,就说明原链表也是空链表。最后直接返回newHead即可。
2、链表的中间节点
题目链接:链表的中间节点
题目:
解题思路: 快慢指针法
解题代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow,*fast;
slow = fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
代码讲解:
所谓快慢指针法就是创建两个结构体指针变量slow和fast,然后让fast每次向前移动两个节点,让slow每次向前移动一个节点,最后如果链表的节点总数为奇数:
那么当fast->next为空指针的时候,这是slow便指向的是中间节点的位置。
当链表节点为偶数的时候:
这时当slow指到中间节点时,fast指向的是空指针。
所以我们while循环的判断条件为fast && fast->next,注意顺序不可以变,必须先先判断fast是否为空,如果为空那么该判定直接为假,后面fast->next就不会被判断,而如果把fast->next放在前面,当链表为奇数的时候,最后fast指向的是空指针,空指针也不会有next,并且编译也会报错。
这题我们就不需要再考虑传过来的head指针是否为空了,因为如果传过来空指针那么就不会进行while循环,直接将slow空指针进行了返回。
3、反转链表
题目链接:反转链表
题目:
**解题思路:**创建三个结构体指针变量改变原链表每个节点所指的方向
解题代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = head;
if(head != NULL)
{
n3 = head->next;
}
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3 != NULL)
{
n3 = n3->next;
}
}
return n1;
}
代码讲解:
我们创建三个结构体指针变量
当链表节点大于2个的时候,三个指针分别指向图示位置,这里n1指的是空指针NULL,然后将n2所指向的下一个节点(n2->next),改变方向指向n1,再将n1向前移(n1 = n2),n2也向前移(n2 = n3),n3也向前移(n3 = n3->next)那么链表就会变成:
while循环重复上面所述步骤,那么最后链表将变成:
当n2为空时,链表的顺序将完全反转,所以while循环判断条件为n2。
while循环中为什么会有一个if判断?
上图中可以看出来n3先指向空指针,但此时结果并不符合我们的预期,需要再经过一次while循环,这时n2也将指向空指针,但是因为n3已经是空指针了,代码中n3 = n3->next就是错误的,这时候我们就不需要再将n3向前移动了,所以我们再n3 = n3->next代码前加上了一个if判断。
对于代码开始判断head是否为空也是同样的道理。
4、合并两个有序链表
题目链接:合并两个有序链表
题目:
解题思路: 创建新链表,判断两个原链表节点大小,进行尾插
解题代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
ListNode* slow,*fast;
slow = fast = NULL;
ListNode* n1 = list1;
ListNode* n2 = list2;
if(n1 == NULL)
{
return n2;
}
if(n2 == NULL)
{
return n1;
}
while(n1 && n2)
{
if(n1->val >= n2->val)
{
if(fast == NULL)
{
slow = fast = n2;
}
else
{
fast->next = n2;
fast = n2;
}
n2 = n2->next;
}
else
{
if(fast == NULL)
{
slow = fast = n1;
}
else
{
fast->next = n1;
fast = n1;
}
n1 = n1->next;
}
}
if(n1)
{
fast->next = n1;
}
if(n2)
{
fast->next = n2;
}
return slow;
}
代码讲解:
因为有可能传过来空链表,所以我们需要考虑空链表的问题:
1.list1为空list2不为空
2.list2为空list1不为空
3.list1和list2都为空
当为上面所述状况时,我们开头的代码,两个if判断即可解决这三种情况。
那么只要是到whille循环的都不是空链表
之后我们就开始进行链表1和链表2每个节点的val值大小判断,并将小的节点尾插进新链表里面
这里还需要判断尾插时,所创建的新链表是否为空,因为空链表的尾插不同于不为空链表的尾插。
跳出while循环,指针n1和指针n2一定会有一个为空指针,另一个还指向链表,直接将还在指向链表的指针尾插进新链表里即可。
5、分割链表
题目链接:分割链表
题目:
解题思路: 创建两个新链表,分别存放大于等于val的节点和小于val的节点,最后在将两个链表连接。
解题代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
if(head == NULL)
{
return head;
}
ListNode* lessHead,*lessTail;
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* greaterHead,*greaterTail;
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* pcur = head;
while(pcur)
{
if(pcur->val < x)
{
lessTail->next = pcur;
lessTail = pcur;
}
else
{
greaterTail->next = pcur;
greaterTail = pcur;
}
pcur = pcur->next;
}
greaterTail->next = NULL;
lessTail->next = greaterHead->next;
ListNode* ret = lessHead->next;
free(greaterHead);
free(lessHead);
return ret;
}
代码讲解:
这题需要注意的就是在最后我们需要将大链表(大于等于val的链表)的最后节点的next置为空指针即:greaterTail->next = NULL,不然代码可能会出现死循环。lessTail->next = greaterHead->next,完成了大链表与小链表的链接。最后将没有使用上的空间进行销毁。
6、环形链表的约瑟夫问题
题目链接:环形链表的约瑟夫问题
题目:
解题思路: 先创建循环链表,然后通过计数器进行节点的删除
解题代码:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param n int整型
* @param m int整型
* @return int整型
*/
typedef struct ListNode ListNode;
ListNode* buyNode(int x)
{
ListNode* newNode = (LisbuyNodetNode*)malloc(sizeof(ListNode));
if(newNode == NULL)
{
exit(1);
}
newNode->val = x;
newNode->next = NULL;
return newNode;
}
ListNode* cresteList(int n)
{
ListNode* phead = buyNode(1);
ListNode* pTail = phead;
for(int i=2; i<=n; i++)
{
pTail->next = buyNode(i);
pTail = pTail->next;
}
pTail->next = phead;
return phead;
}
int ysf(int n, int m ) {
// write code here
ListNode* pcur = cresteList(n);
ListNode* prev = NULL;
int count = 1;
while(pcur != pcur->next)
{
if(count != m)
{
prev = pcur;
pcur = pcur->next;
count++;
}
else
{
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;
}
}
return pcur->val;
}
代码讲解:
首先我们要创建一个循环链表,通过cresteList和buyNode函数即可完成。
我们假设m为2,n为5。
那么实际画图如上面所示,开始pcur指向节点1,然后pcur向后移一次,同时将prev指向pcur的位置,此时计数器count要加加,那么count就等于m,要进行节点的删除,可以看上面解题代码,执行删除的操作时我们还需要将删除节点的前后节点进行连接,prev->next = pcur->next;执行的就是连接操作,然后释放掉节点pcur后要将pcur指向删除节点的下一个节点,也就是pcur = prev->next;注意,此时prev已经和第三个节点连接,所以prev->next指向的就是删除节点的下一个节点。
以此循环上面步骤,最后剩下的节点会自己指向自己,那么就将跳出while循环,返回对应val指即可。
完结撒❀
如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友