jQuery网站建设中倒计时代码,惠州有没有做网站,春考网站建设,推进网站集约化建设的做法今天讲解两道链表OJ题目。
1.链表的中间节点 给你单链表的头结点 head #xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点#xff0c;则返回第二个中间结点。 示例 输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[3,4,5]
解释#xff1a;链表只有一个…今天讲解两道链表OJ题目。
1.链表的中间节点 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 示例 输入head [1,2,3,4,5]
输出[3,4,5]
解释链表只有一个中间结点值为 3 方法1【 双指针】
时间复杂度O(N)
思想两个指针faster的速度是slow两倍则当faster走到结尾时slow则走到链表中间。
易错循环条件
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode*fasterhead;struct ListNode*slowhead;while(faster faster-next)//条件没想到{fasterfaster-next-next;slowslow-next;}return slow;
} 2.移除链表元素 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 输入head [1,2,6,3,4,5,6], val 6
输出[1,2,3,4,5]方法1【三指针--无哨兵位】
时间复杂度O(N)
思想三个指正cur负责对比valtmp负责存储删除元素的下一个元素地址prve负责存储删除元素的上一个元素地址
易错
记住prve是cur的前一个元素那么它从NULL开始循环条件记得处理头节点和尾节点造成野指针的错误❌ /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*curhead;struct ListNode*prveNULL;while(cur){if(cur-val val){struct ListNode*tmpcur-next;free(cur);if(prve){prve-nexttmp;} else{headtmp;} curtmp;}else{prvecur;curcur-next;}}return head;} 方法2【双指针---无哨兵位】 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*newheadNULL;struct ListNode*tailNULL;struct ListNode*curhead;while(cur){if(cur-val ! val){if(newhead NULL){newheadtailcur;}else{tail-nextcur;tailtail-next;}curcur-next;}else{struct ListNode*tmpcur-next;free(cur);curtmp;}if(tail){tail-nextNULL;}} return newhead;
}//❌改进 那有哨兵位怎么写呢
当然这道题还可以联系前面顺序表移除val。
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱2784139418qq.com】
