宁波专业网站seo公司,福州小程序开发公司列表,网站上线模板,seo引擎搜索网站关键词这里写目录标题 反转链表合并两个有序链表分割链表 反转链表
1、题目#xff1a; 2.思路 思路1#xff1a;建立一个newHead,取一个节点进行头插。具体做法如下#xff01; 建立一个newHead(新头)#xff0c;由于一个节点里面存的是下一个节点的地址#xff0c;如果取… 这里写目录标题 反转链表合并两个有序链表分割链表 反转链表
1、题目 2.思路 思路1建立一个newHead,取一个节点进行头插。具体做法如下 建立一个newHead(新头)由于一个节点里面存的是下一个节点的地址如果取一个节点下来进行头插那么要取的下一个节点的地址找不到因此定义n1,n2,n1用来往下拿结点进行头插n2预备下一次要的节点 代码如下
/*** 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* newHead NULL;//n1为向下取得插入的节点struct ListNode* n1 head;//n2是给n1准备的节点struct ListNode* n2 head-next;while(n1){n1-next newHead;newHead n1;n1 n2;//当n2为NULL时n2没有取得节点了if(n2){n2 n2-next;}}return newHead;
}思路2把指针翻转把指针反转的意思是把存节点的地址交换定义三个指针n1,n2,n3,n1 NULL,n2 head,n3 head-next,n2为第一个节点翻转n2-next n1,n2里面原来存的地址找不到因此要n3存下一个节点的地址这样这个题就可以反转了
struct ListNode* reverseList(struct ListNode* head) {if(head NULL){return NULL;}struct ListNode* n1 NULL;struct ListNode* n2 head;struct ListNode* n3 head-next;while(n2){n2-next n1;n1 n2;n2 n3;if(n3){n3 n3-next;}}return n1;
}合并两个有序链表
1、题目 2、思路 这个题建立一个新链表取小的数尾插即可这儿有一些技巧可以建立一个头结点直接尾插这样就省去了考虑newHead为NULL的情况这个方法在一些题中有妙用
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {if(l1NULL){return l2;}if(l2NULL){return l1;}//处理这个建立一个头节点把为NULL的一种可能性去掉struct ListNode* tmp (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail tmp;while(l1l2){if(l1-vall2-val){tail-next l1;tail l1;l1 l1-next;}else{tail-next l2;tail l2;l2 l2-next;}}if(l1){tail-next l1;}if(l2){tail-next l2;}return tmp-next;
}下面是一个正常的做法
/*** 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* newHead,*tail;newHead NULL;while(l1l2){if(l1-vall2-val){if(newHead NULL){newHead tail l1;}else{tail-next l1;tail l1;}l1 l1-next;}else{if(newHead NULL){newHead tail l2;}else{tail-next l2;tail l2;}l2 l2-next;}}if(l1){tail-next l1;}if(l2){tail-next l2;}return newHead;
}分割链表
1、题目 2、思路 建立两个链表一个是x的链表一个是x的链表最后把这两个链表组合起来返回头即可
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///建立两个链表
//一个小于x
//一个大于等于x
struct ListNode* partition(struct ListNode* head, int x){/* ifhead NULL{return NULL;}*/struct ListNode* litterHead ( struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* litterTail litterHead;struct ListNode* biggerHead ( struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* biggerTail biggerHead;struct ListNode* cur head;while(cur){if(cur-valx){litterTail-next cur;litterTail cur;cur cur-next;}else{biggerTail-next cur;biggerTail cur;cur cur-next;}}biggerTail-next NULL;litterTail-next biggerHead-next;return litterHead-next;
}完结
