赞
踩
目录
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
示例 2:输入:head = [], val = 1
输出:[]
示例 3:输入:head = [7,7,7,7], val = 7
输出:[]
链接:https://leetcode.cn/problems/remove-linked-list-elements
思路:定义一个cur的指针,去找值为val的结点,然后再定义一个prev去保存cur的前一个位置,每次当cur找到值为val的结点时,我们要让prev->next = val->next , 然后释放(free)掉cur找到的这个结点, 然后再让cur=prev->next
终止条件:就是当cur走到空就停止了
(要考虑第一个结点的值就是val的这种情况,就是头删了)
这里再演示一下头删
- // 结构体
- //struct ListNode {
- // int val;
- //struct ListNode *next;
- //};
-
- struct ListNode* removeElements(struct ListNode* head, int val)
- {
- //找val的值为val的结点,把找到的结点free掉就可以了
- struct ListNode* prev=NULL;
- struct ListNode* cur=head;
- while(cur)
- {
- if(cur->val==val)
- {
- //1.头删
- if(cur==head)
- {
- head=head->next;
- free(cur);
- cur=head;
- }
- //2.中间删除
- else
- {
- prev->next=cur->next;
- free(cur);
- cur=prev->next;
- }
- }
- else
- {
- prev=cur;
- cur=cur->next;
- }
- }
- return head;
- }

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:输入:head = []
输出:[]
链接:https://leetcode.cn/problems/reverse-linked-list
再原链表中进行反转,需要定义三个指针(prev cur next)
next负责记录下一个位置,cur负责反转,prev负责迭代记录。
最后返回我们的prev,就是我们反转后新的头。
这个是直到 cur走到空了,才停下来.
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- //};
-
- struct ListNode* reverseList(struct ListNode* head)
- {
- struct ListNode* prev=NULL;
- struct ListNode* cur=head;
- struct ListNode* next=head;
- while(cur)
- {
- next=cur->next;
- //翻转
- cur->next=prev;
- //迭代往后走
- prev=cur;
- cur=next;
- }
- return prev;
- }

再创建一个新的链表来进行头插,把原链表中的结点从前往后遍历,依次头插到新的链表中,然后再返回我们新链表的头就可以了。
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- //};
-
- struct ListNode* reverseList(struct ListNode* head)
- {
- //头插的思路
- struct ListNode* newhead=NULL;
- struct ListNode* cur=head;
- struct ListNode* next=head;
- while(cur)
- {
- next=cur->next;
- cur->next=newhead;
- newhead=cur;
- cur=next;
- }
- return newhead;
- }

3.思路3:
使用带有哨兵位的头结点来解决这道题,也是头插的思路
( 再创建一个新的链表来进行头插,把原链表中的结点从前往后遍历,依次头插到新的链表中,然后再返回我们新链表的头就可以了。)
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- //};
-
- //使用带有哨兵位的头结点的链表来解决这道题
- //依旧还是头插的思路
- struct ListNode* reverseList(struct ListNode* head)
- {
- struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
- newhead->next=NULL;
- struct ListNode* cur=head;
- struct ListNode* next=head;
- while(cur)
- {
- next=cur->next;
- cur->next=newhead->next;
- newhead->next=cur;
- cur=next;
- }
- struct ListNode* list=newhead->next;
- free(newhead);
- return list;
- }

给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2:输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。
链接:https://leetcode.cn/problems/middle-of-the-linked-list
定义2个指针,slow和fast
slow一次走一步,fast一次走2步,链表的结点数有2种情况(奇数和偶数)
//1.如果是奇数个结点,那么应该是当fast到达链表尾部的时候,停下来
//2.如果是偶数个结点,那么应该是当fast指向空的时候,停下来
所以停下来的条件是fast==NULL或者fast->next==NULL .
此时slow的位置就是链表的中间结点了。
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- //};
-
- struct ListNode* middleNode(struct ListNode* head)
- {
- //定义快慢指针,一个一次走一步,一个一次走2步
- struct ListNode* slow=head;
- struct ListNode* fast=head;
- //1.如果是奇数个结点,那么应该是当fast到达链表尾部的时候,停下来
- //2.如果是偶数个结点,那么应该是当fast指向空的时候,停下来
- while(fast&&fast->next)
- {
- slow=slow->next;
- fast=fast->next->next;
- }
- return slow;
- }

输入一个链表,输出该链表中倒数第k个结点。
示例一:
输入:
1,{1,2,3,4,5}返回值:
{5}
// 1.fast先走k步,然后再让fast和slow一起走,当最后fast为空的时候,停下来
// 这个时候的slow就是链表中的倒数第k个结点
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- // };
-
- struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
- {
- //1.fast先走k步,然后再让fast和slow一起走,当最后fast为空的时候,停下来
- //这个时候的slow就是链表中的倒数第k个结点
-
- struct ListNode* slow=pListHead;
- struct ListNode* fast=pListHead;
- while(k--)
- {
- if(fast==NULL)
- return NULL;
- else
- {
- fast=fast->next;
- }
- }
- while(fast)
- {
- fast=fast->next;
- slow=slow->next;
- }
- return slow;
- }

// 2.fast先走k-1步,然后再让fast和slow一起走,当最后fast为链表的尾时,停下来
// 这个时候的slow就是链表中的倒数第k个结点
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- // };
-
- struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
- {
- //2.fast先走k-1步,然后再让fast和slow一起走,当最后fast为链表的尾时,停下来
- //这个时候的slow就是链表中的倒数第k个结点
- struct ListNode* slow=pListHead;
- struct ListNode* fast=pListHead;
- while(--k)
- {
- if(fast==NULL)
- {
- return NULL;
- }
- else
- {
- fast=fast->next;
- }
- }
- if(fast==NULL)
- return NULL;
- while(fast->next)
- {
- fast=fast->next;
- slow=slow->next;
- }
- return slow;
- }

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:输入:l1 = [], l2 = []
输出:[]
示例 3:输入:l1 = [], l2 = [0]
输出:[0]
链接:https://leetcode.cn/problems/merge-two-sorted-lists
1.新建一个新的链表,然后把2个要合并的有序链表的结点进行比较,然后把比较之后小的那个结点尾插到新的链表里面。
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- // };
-
- struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
- {
- if(list1==NULL)
- return list2;
- if(list2==NULL)
- return list1;
- struct ListNode* cur1=list1;
- struct ListNode* cur2=list2;
- struct ListNode* newhead=NULL;
- struct ListNode* tail=NULL;
- while(cur1&&cur2)
- {
- if(cur1->val<cur2->val)
- {
- if(newhead==NULL)
- {
- newhead=cur1;
- tail=cur1;
- cur1=cur1->next;
- }
- else
- {
- tail->next=cur1;
- tail=cur1;
- cur1=cur1->next;
- }
- }
- else
- {
- if(newhead==NULL)
- {
- newhead=cur2;
- tail=cur2;
- cur2=cur2->next;
- }
- else
- {
- tail->next=cur2;
- tail=cur2;
- cur2=cur2->next;
- }
- }
- }
- if(cur1!=NULL)
- {
- tail->next=cur1;
- }
- if(cur2!=NULL)
- {
- tail->next=cur2;
- }
- return newhead;
- }
-

新建一个新的链表,然后把2个要合并的有序链表的结点进行比较,然后把比较之后小的那个结点尾插到新的链表里面。
2.和第一种方法相比就是在判断是否要头插的那里有点不一样,其他的思路和做法都是一样的。
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- // };
-
- struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
- {
- if(list1==NULL)
- return list2;
- if(list2==NULL)
- return list1;
- struct ListNode* cur1=list1;
- struct ListNode* cur2=list2;
- struct ListNode* newhead=NULL;
- struct ListNode* tail=NULL;
- if(cur1->val<cur2->val)
- {
- newhead=cur1;
- tail=newhead;
- cur1=cur1->next;
- }
- else
- {
- newhead=cur2;
- tail=newhead;
- cur2=cur2->next;
- }
- while(cur1&&cur2)
- {
- if(cur1->val<cur2->val)
- {
- tail->next=cur1;
- tail=cur1;
- cur1=cur1->next;
- }
- else
- {
- tail->next=cur2;
- tail=cur2;
- cur2=cur2->next;
- }
- }
- if(cur1!=NULL)
- {
- tail->next=cur1;
- }
- if(cur2!=NULL)
- {
- tail->next=cur2;
- }
- return newhead;
- }

新建一个新的链表,然后把2个要合并的有序链表的结点进行比较,然后把比较之后小的那个结点尾插到新的链表里面。
3.这个第三种方法的思路,简单来说和上面不同的点:就是新创建的是一个带有哨兵位的头结点的链表。
- //结构体
- // struct ListNode {
- // int val;
- // struct ListNode *next;
- // };
-
- struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
- {
- struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
- struct ListNode* tail=newhead;
- if(list1==NULL)
- return list2;
- if(list2==NULL)
- return list1;
- struct ListNode* cur1=list1;
- struct ListNode* cur2=list2;
- while(cur1&&cur2)
- {
- if(cur1->val<cur2->val)
- {
- tail->next=cur1;
- tail=cur1;
- cur1=cur1->next;
- }
- else
- {
- tail->next=cur2;
- tail=cur2;
- cur2=cur2->next;
- }
- }
- if(cur1!=NULL)
- {
- tail->next=cur1;
- }
- if(cur2!=NULL)
- {
- tail->next=cur2;
- }
- struct ListNode* list=newhead->next;
- free(newhead); // malloc 申请的空间,不使用了就要free(释放掉)
- return list;
- }
-
-

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。