elementor做视频网站,外贸营销平台推广,模仿建设银行网站,雄安投资建设集团网站一、移除链表元素 移除链表中值为val的元素#xff0c;并返回新的头节点
思路#xff1a;
题目上这样说#xff0c;我们就可以创建一个新的链表#xff0c;将值不为val的节点#xff0c;尾插到新的链表当中#xff0c;最后返回新链表的头节点。
typedef struct ListNo…一、移除链表元素 移除链表中值为val的元素并返回新的头节点
思路
题目上这样说我们就可以创建一个新的链表将值不为val的节点尾插到新的链表当中最后返回新链表的头节点。
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {if(headNULL){return NULL;}ListNode* newhead (ListNode*)malloc(sizeof(ListNode));ListNode* ptail head;ListNode* pcur newhead;while (ptail) {if (ptail-val ! val) {pcur-next ptail;pcur pcur-next;}ptail ptail-next;}pcur-nextNULL;ListNode* ret newhead-next;free(newhead);newhead NULL;return ret;
} 当然这个题还有其他思路。
二、反转链表 将链表反转并返回反转后的链表的头节点
思路 创建三个指针变量l1l2l3指针初始指向如下图遍历链表先让l3l2-next再将l2的next指针指向l2再l1指向l2l2指向l3l2下一个节点直到遍历结束结束条件为l2等于NULL此时l1指向的就是反转后的链表的头节点。
根据题目给的示例来分析
遍历数组循环进行一次 l2不等于NULL循环继续 l2不等于NULL循环继续 l2不等于NULL循环继续 l2仍然不等于NULL循环继续 到这里l2已经遍历到了NULL循环结束此时l1指向的就是反转后链表的头节点直接返回即可。
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {ListNode* l1,*l2,*l3;l1NULL;l2head;while(l2){l3l2-next;l2-nextl1;l1l2;l2l3;}return l1;
}
三、链表的中间节点 看到这个题本人一开始的想法是遍历一遍链表记录链表的节点个数然后再遍历一次链表寻找链表的中间节点这样实现非常麻烦现在使用一种新的方法来解决这个问题
思路快慢指针 定义两个快慢指针fast和slow刚开始都指向链表的头节点fast每次向前走两个节点而slow指针每次向前走一个节点最后当fast指针或者fast的next指针为NULL遍历结束此时slow指向的就是链表的中间节点。
根据题所给的示例分析 链表个数为奇数
fastfsat-next-next;
slowslow-next; 遍历到这里fast的next指针为空循环结束此时slow指向的就是链表的中间节点。 链表的节点数为偶数 fastfsat-next-next;
slowslow-next; 循环到这里fast为空循环结束此时slow指向的节点就是链表的中间节点。
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {if(headNULL){return NULL;}ListNode* fasthead;ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;
}
四、合并两个有序链表 合并两个有序链表这里创建一个新的链表将两个链表中较小小的数据依次尾插到新链表中最后返回新链表的头节点即可。 注意这里需要注意初始的两个链表可能为空这里需要进判断如果list1为空就返回list1如果list2为空就返回list1。
根据题目示例分析 比较l1和l2指向的节点的值大小l1-vall2-vall1的不小于l2的将l2指向节点尾插到新链表 此时l1-val l2-val将l1指向的节点尾插到新链表 此时l1-val l2-val将l1指向的节点尾插到新链表
比较l1和l2指向的节点的值大小l2-val l1-val将l2指向节点尾插到新链表 比较l1和l2指向的节点的值大小l1-vall2-vall1的不小于l2的将l2指向节点尾插到新链表 l2为空循环结束这里l1的节点还没全部插到新链表中这里直接 ptail-nextl1;即可。
注这里使用动态内存来给newhead开辟空间记得将其释放掉养成好习惯。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1NULL){return list2;}if(list2NULL){return list1;}ListNode* l1list1;ListNode* l2list2;ListNode* newhead(ListNode*)malloc(sizeof(ListNode));ListNode* ptailnewhead;while(l1 l2){if(l1-vall2-val){ptail-nextl1;l1l1-next;}else{ptail-nextl2;l2l2-next;} ptailptail-next;}if(l1){ptail-nextl1;}if(l2){ptail-nextl2;}ListNode* retnewhead-next;free(newhead);newheadNULL;return ret;
}
五、链表分割
将链表小于x的节点排在其余节点之前不能改变原来顺序最后返回排序好的链表的头指针。
思路 创建两个链表一个链表l1存放值小于val的节点另一个链表l2存放值大于等于val的节点。最后将两个链表连接起来返回l1链表的头节点即可。
这里需要注意再l2链表的结尾要将尾节点的next指针置为NULL
#include cstddef
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* list1,*l1;l1list1(ListNode*)malloc(sizeof(ListNode));ListNode* list2, *l2;l2list2(ListNode*)malloc(sizeof(ListNode));ListNode* ptailpHead;while(ptail){if(ptail-valx){//尾插到l1里l1-nextptail;l1l1-next;}else{l2-nextptail;l2l2-next;}ptailptail-next;}l2-nextNULL;l1-nextlist2-next;ListNode* retlist1-next;free(list1);free(list2);list1list2NULL;return ret;}
};
