留学生做留服证明在哪个网站,安徽省建设工程资料上传网站,网站建设说明书,网络营销策略分析论文文章目录 一、反转链表1、程序详解2、代码 二、相交链表1、程序详解2、代码 三、链表的中间节点1、程序详解2、代码 四、回文链表1、程序详解2、代码 一、反转链表
1、程序详解
题目#xff1a;给定单链表的头节点 head #xff0c;请反转链表#xff0c;并返回反转后的链… 文章目录 一、反转链表1、程序详解2、代码 二、相交链表1、程序详解2、代码 三、链表的中间节点1、程序详解2、代码 四、回文链表1、程序详解2、代码 一、反转链表
1、程序详解
题目给定单链表的头节点 head 请反转链表并返回反转后的链表的头节点。
示例 将链表逆置
方法一创建新链表。 遍历原链表并将节点依次头插到新链表中。方法二创建三个指针 。 通过指针的不断移动依次完成反转 创建三个结构体指针n1、n2、n3 令 n1指向空n2指向头节点n3指向头结点的下一个节点 分为两个步骤 1、n2-nextn1, 令n2指向n1 2、n1、n2、n3不断向后移动
2、代码
struct ListNode* reverseList(struct ListNode* head){if(headNULL)return head;struct ListNode* n1, *n2, *n3;n1NULL, n2head, n3n2-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;
}二、相交链表
1、程序详解
题目给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 注根据一个节点只能有一个next相交链表一定是Y型的。
当然也有两种方法一定要用地址来判断
方法一暴力求解双层循环。 A链表中的节点依次与B链表中的所有节点相比较此时,时间复杂度为O(N^2)方法二双指针 1、找出A链表与B链表长度相减得差值k 2、让长链表的指针先走k步 3、A与B的指针同时走并相比较
2、代码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode * curA headA, *curB headB;int len1 1, len21; //用len1len2来记录两链表的长度但在循环里面少记录一个故初始化为1while(curA-next){curA curA-next;len1;}while(curB-next){curB curB-next;len2;}//若尾节点不相等则两链表一定不相交if(curA ! curB){return NULL;}//相交//找出长链表和短链表struct ListNode * longList headA, *shortList headB;int gre abs(len1-len2);if(len1len2){longList headB;shortList headA;}//找出长短链表后让长链表先走差步while(gre--){longList longList-next;}//两链表同时走while(longList ! shortList){longList longList-next;shortList shortList-next;}return longList;
}三、链表的中间节点
1、程序详解
题目给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。
方法快慢指针 若使快指针的速度始终是慢指针的二倍那么当快指针走到链表结尾慢指针刚好走到链表的中间。
2、代码
struct ListNode* middleNode(struct ListNode* head) {//快慢指针,快指针走两步慢指针走一步struct ListNode* fast head, *slow head;while(fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}四、回文链表
1、程序详解
题目给你一个单链表的头节点 head 请你判断该链表是否为 回文链表。如果是返回 true 否则返回 false 。
方法 1、找到中间节点 2、将中间节点之后的节点进行反转 3、将中间节点之前的与反转后的节点 的val值进行比较
故回文链表综合了 反转链表与链表的中间节点了解了这两个题目方法后我们只需写进行比较的代码。
2、代码
//找中间节点
struct ListNode *fac1(struct ListNode * head)
{struct ListNode * fasthead, *slowhead;while(fast fast-next){slowslow-next;fastfast-next-next;}return slow;
}
//反转
struct ListNode *fac2(struct ListNode * head)
{struct ListNode * n1, *n2, *n3;n1NULL, n2head, n3n2-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;
}
bool isPalindrome(struct ListNode* head) {struct ListNode * mid fac1(head);struct ListNode * rmid fac2(mid);//进行比较while(rmid head){if(rmid-val ! head-val)return false;rmidrmid-next;headhead-next;}return true;
}
