来安县城乡建设网站,网站建设讲师招聘,申请注册电子邮箱,厦门功夫广告设计网站建设工作室一、反转链表
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 思路一#xff1a;翻转单链表指针方向
这里解释一下三个指针的作用#xff1a;
n1#xff1… 一、反转链表
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路一翻转单链表指针方向
这里解释一下三个指针的作用
n1记录上一个节点如果是第一个就指向空
n2记录此节点的位置
n3记录下一个节点的位置让翻转后能找到下一个节点防止丢失指针的地址
/** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {if(head NULL){return NULL;}//初始条件struct ListNode* n1 NULL,*n2 head,*n3 n2-next;//结束条件while(n2){//迭代过程n2-next n1;n1 n2;n2 n3;if(n3)n3 n3-next;}return n1;
} 思路二:头插法
取原链表节点头插到新链表
/** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur head;struct ListNode* newHead NULL;while(cur){struct ListNode* next cur-next;//头插cur-next newHead;newHead cur;cur next;}return newHead;
} 二、链表的中间结点
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路一单指针法 时间复杂度O(N*1.5)其中 N 是给定链表的结点数目。 空间复杂度O(1)只需要常数空间存放变量和指针。
我们可以对链表进行两次遍历。第一次遍历时我们统计链表中的元素个数 N第二次遍历时我们遍历到第 N/2 个元素链表的首节点为第 0 个元素时将该元素返回即可。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {int n 0;struct ListNode*cur head;while(cur ! NULL){n;cur cur-next;}int k 0;cur head;while(k n/2){k;cur cur-next;}return cur;
}
思路二快慢指针法 时间复杂度O(N)其中 N 是给定链表的结点数目。 空间复杂度O(1)只需要常数空间存放 slow 和 fast 两个指针。 我们可以优化思路一用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步fast 一次走两步。那么当 fast 到达链表的末尾时slow 必然位于中间。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow head,*fast head;while(fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}
三、合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路一迭代法:
定义一个头指针和一个尾指针从小到大依次尾插直到一个链表为空时结束 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1 NULL) return l2;if(l2 NULL)return l1;struct ListNode* head NULL, *tail NULL;while(l1 ! NULL l2 ! NULL){if(l1-val l2-val){//尾插if(tail NULL){head tail l1;}else{tail-next l1;tail tail-next;}l1 l1-next;}else{if(tail NULL){head tail l2;}else{tail-next l2;tail tail-next;}l2 l2-next;}}if(l1)tail-next l1;if(l2)tail-next l2;return head;
}
优化一:
先确定头结点然后再循环判断val大小尾插
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1 NULL) return l2;if(l2 NULL)return l1;struct ListNode* head NULL, *tail NULL;//先确定头节点if(l1-val l2-val){head tail l1;l1 l1-next;}else{head tail l2;l2 l2-next;}while(l1 l2){//尾插if(l1-val l2-val){ tail-next l1;l1 l1-next;}else{tail-next l2;l2 l2-next;}tail tail-next;}if(l1)tail-next l1;if(l2)tail-next l2;return head;
}优化二:
设置一个哨兵位的头节点然后再去尾插。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1 NULL) return l2;if(l2 NULL)return l1;struct ListNode* head NULL, *tail NULL;//哨兵位的头节点head tail (struct ListNode*)malloc(sizeof(struct ListNode));while(l1 l2){//尾插if(l1-val l2-val){ tail-next l1;l1 l1-next;}else{tail-next l2;l2 l2-next;}tail tail-next;}if(l1)tail-next l1;if(l2)tail-next l2;struct ListNode* first head-next;free(head);return first;
}思路二递归法
这是题解中大佬的一个解法以迭代的思路写递归尤为惊人
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){/*if判断1.如果l1为空返回l22.如果l2为空返回l13.如果l1的值小于l2比较l1的next值和l2并把值赋给l1的下一个返回l14.反之比较l1和l2的next值并把值赋给l2的下一个返回l2*/if (l1 NULL) {return l2;} else if (l2 NULL) {return l1;} else if (l1-val l2-val) {l1-next mergeTwoLists(l1-next, l2);return l1;} else {l2-next mergeTwoLists(l1, l2-next);return l2;}
} 因为有缓冲区的存在C语言在操作文件的时候需要做刷新缓冲区或者在文件操作结束的时候关闭文件。 如果不做可能导致读写文件的问题。
今天就先到这了 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信!
