网站被做镜像什么意思,网站建设代码容易出错,河源正规网站建设价格,怎么用ps做网站框架一、俩数相加
2.俩数相加#xff08;题目链接#xff09; 思路#xff1a;这题题目首先要看懂#xff0c;以示例1为例 即 342465807#xff0c;而产生的新链表为7-0-8. 可以看成简单的从左向右#xff0c;低位到高位的加法运算#xff0c;4610#xff0c;逢…一、俩数相加
2.俩数相加题目链接 思路这题题目首先要看懂以示例1为例 即 342465807而产生的新链表为7-0-8. 可以看成简单的从左向右低位到高位的加法运算4610逢10进1新链表第三位为341第二位进的1),需要注意的的点是当9-9-9和9-9-9-9相加相当于9-9-9-0和9-9-9-9相加 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;ListNode * ListBuyNode(int x){ListNode * node(ListNode*)malloc(sizeof(ListNode));if(nodeNULL){perror(malloc fail:);return NULL;}node-valx;node-nextNULL;return node;}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {int ret0;ListNode *head(ListNode*)malloc(sizeof(ListNode));//带头单链表ListNode*pcurhead;while(l1||l2||ret){if(l1){retretl1-val;}if(l2){retretl2-val;}ListNode *nodeListBuyNode(ret%10);pcur-nextnode;pcurpcur-next;if(l1){l1l1-next;}if(l2){l2l2-next;}retret/10;}return head-next;
} 解析这里使用的是带头单链表不用考虑头节点初始化问题还有一点是当l1和l2都走完时还要确定进位是否为0不为0新链表还得在加一个节点储存进位。 测试及结果 二、回文链表
234.回文链表题目链接 思路1将链表内容复制到数组里面 2使用双指针法判断是否为回文。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool isPalindrome(struct ListNode* head) {assert(head);int arr[100000]{0};int k0;ListNode*pcurhead;while(pcur){arr[k]pcur-val;k;pcurpcur-next;}for(int i0,jk-1;ij;i,j--){if(arr[i]!arr[j]){return false;}}return true;
}
三、相交链表
160.相交链表题目链接 思路这道题的思路比较巧妙相交链表最关键是节点重合所以判断条件是节点相等不是节点的val相等 。 若链表其中一个为NULL,则必定不相交返回NULL. 分类讨论 1链表不相交假设pheadA的长度为m,headB的长度为n) 1若mn,俩链表同时遍历完相等为NULL 2若m!n,headA往后遍历若遍历结束则返回到headB的头节点,headB往后遍历若遍历结束则返回到headA的头节点,当遍历mn次他们都相等为NULL 2)链表相交假设pheadA的长度为m,headB的长度为n相交点到headA的头节点距离为a,相交点到headB的头节点距离为b,相交点到末尾的长度为c) 注acm,bcn 1若mn,在遍历完第一遍之前必定有headAheadB!NULL 2若m!n,headA往后遍历若遍历结束则返回到headB的头节点,headB往后遍历若遍历结束则返回到headA的头节点,当headA遍历acb次headB遍历bca,同时到达相交点headAheadB!NULL /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode *p1headA;ListNode*p2headB;if(p1NULL){return NULL;}if(p2NULL){return NULL;}while(p1!p2){p1 p1 NULL ? headB : p1-next;p2 p2 NULL ? headA : p2-next;}//p1与p2不相交则为NULL;p1与p2相交则为不为NULLif(p1NULL){return NULL;}return p1;
}
四、删除链表倒数第N个节点
19.删除链表的倒数第N个节点 解法一快慢指针这里使用无头链表需要对删除头节点额外考虑 typedef struct ListNode ListNode;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {assert(head);ListNode* fast,*slow;fastslowhead;if(head-nextNULL)//只有一个节点{free(head);headNULL;return NULL;}//至少2个节点while(n--){fastfast-next;}if(fastNULL)//删除头节点{headhead-next;return head;}while(fast-next){fastfast-next;slowslow-next;}ListNode *delslow-next;slow-nextdel-next;free(del);delNULL;return head;
} 优化快慢指针引进头节点哑节点 typedef struct ListNode ListNode;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {assert(head);ListNode* fast,*slow;ListNode*node(ListNode*)malloc(sizeof(ListNode));node-nexthead;fastslownode;int mn1;while(m--){fastfast-next;}while(fast){fastfast-next;slowslow-next;}ListNode*delslow-next;slow-nextdel-next;free(del);delNULL;return node-next;
} 解法二遍历链表找到链表节点数L,用删除指定位置节点方式删除第L-n1)个节点即可
