网站做qq发送链接,手机网站模板网,网页设计结束语,建站网站推荐前言
关于环形指针与快慢指针是算法题中的常客#xff0c;如果能掌握将是我们的一大助力#xff01;
1.快慢指针 1 移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/description/
1#xff09;思路
这道题可以用一个新链表来保存原链表中不…前言
关于环形指针与快慢指针是算法题中的常客如果能掌握将是我们的一大助力
1.快慢指针 1 移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/description/
1思路
这道题可以用一个新链表来保存原链表中不是val的值最后返回新链表的头节点就行。给一个newhead和ptail作用用来走链表给一个purc用来遍历原链表以找到不是val的节点。
2解析 typedef struct ListNode slnode;
struct ListNode* removeElements(struct ListNode* head, int val) {slnode*newhead NULL;slnode*ptail NULL;slnode* purchead;if(headNULL)//给的原链表是空链表时{return NULL;} else//不是空链表{ while(purc){ if(purc-val ! val)//当purc中的数据不是val时就尾插{if(newheadNULL)//处理第一个不是val的节点{newheadptailpurc;}else//新链表有了第一个节点{ptail-nextpurc;ptailptail-next;}}purcpurc-next;}if(ptail)//为了断开和原链表的链接ptail-nextNULL;return newhead;}
}2 反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
1)思路
反转链表整体来说是比较简单的。创建三个指针就能解决 n1置为nulln2置为原链表的头指针n3置为head-next然后开始循环让n2指向n1把n1给n2n2给n3n3给n3-next,知道n2为空时n1就是新链表的头节点。
2解析 typedef struct ListNode slnode;
struct ListNode* reverseList(struct ListNode* head) {if(headNULL)//如果处理的是空链表{return NULL;}else//不是空链表{slnode* n1,*n2,*n3;n1NULL;n2head;n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)//如果n3已经走到nulln3就不用走了n3n2-next;}return n1;}
}3 链表的中间结点快慢指针
https://leetcode.cn/problems/middle-of-the-linked-list/description/
1思路
这道题经典的快慢指针创建一个快指针和一个慢指针开始时两个指针都指向头节点随后慢指针走一步快指针走两步当快指针走到最后一个节点链表有奇数个节点或者为空时链表有偶数个节点慢指针就走到了中间节点
2解析 typedef struct ListNode slnode;
struct ListNode* middleNode(struct ListNode* head) {slnode* quickhead;slnode* slowhead;if(headNULL)//处理空链表{return NULL;}else{while(quick quick-next)//这里quick不能为空是为了处理偶数个结点的情况{ slowslow-next;quickquick-next-next;//慢指针走一步快指针走两步}return slow;}
}4 合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/description/
1思路
这道题与之前的合并有序数组思路大致一致 合并有序数组大家可以去看一看
2解析
typedef struct ListNode slnode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1NULL)//处理空链表{return list2;}else if(list2NULL){return list1;}else//没有空链表{ slnode* newhead NULL;slnode* newtail NULL;while(list1 list2){if(list1-val list2-val)//比较,{if(newheadNULL)//处理第一个节点{newheadnewtaillist2; list2list2-next;}else{newtail-nextlist2;newtailnewtail-next;list2list2-next;}}else{if(newheadNULL)//处理第一个节点{newheadnewtaillist1;list1list1-next;}else{newtail-nextlist1;newtailnewtail-next;list1list1-next;}} }//处理有链表提前轮空if(list1)newtail-nextlist1;if(list2)newtail-nextlist2;return newhead;}
}5 链表分割
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
1思路
创建两个新链表一个放小于x的数据一个放大于x的数据最后连接两个链表
2解析
#include cstddef
class Partition {
public:ListNode* partition(ListNode* pHead, int x){// write code hereListNode*lesshead,*lesstail,*bighead,*bigtail;lesshead lesstail (ListNode*)malloc(sizeof(ListNode));//充当哨兵位bighead bigtail (ListNode*)malloc(sizeof(ListNode));ListNode*purcpHead;while(purc){ if(purc-val x)//放到小链表里{lesstail-nextpurc;lesstaillesstail-next; }else//放到大链表里{bigtail-nextpurc;bigtailbigtail-next;}purc purc-next;}bigtail-nextNULL;//防止形成环形链表成死循环lesstail-nextbighead-next;//连接大小链表ListNode* retlesshead-next;free(lesshead);free(bighead);lessheadbigheadNULL;return ret;}
};
