怎么上传网站模板,电子商务seo优化,南康做网站,玉林市网站建设目录
一、找出并返回链表的中间结点
二、输出链表中倒数第k个结点
三、判断链表中是否有环
四、两个单链表相交 一、找出并返回链表的中间结点
给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 要求#xff1a;只遍历…目录
一、找出并返回链表的中间结点
二、输出链表中倒数第k个结点
三、判断链表中是否有环
四、两个单链表相交 一、找出并返回链表的中间结点
给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 要求只遍历一遍链表
可以使用快慢指针fast 一次走两步slow 一次走一步。当 fast NULL偶数个结点或者 fast-next NULL奇数个结点就停止返回 slow。
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow, *fast; slow fast head; while(fast fast-next){slow slow-next; fast fast-next-next;}return slow;
}注意
1、一次性定义多个指针时第二个及以后的指针名前面都要加 * 。
2、while 括号内是循环继续的条件。
二、输出链表中倒数第k个结点
输入一个链表,输出该链表中倒数第k个结点。 要求只遍历一遍链表
快慢指针fast 先走 k - 1 步然后 fast 和 sliow 同时走直到 fast 走到链表的最后一个结点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* slow, *fast; slow fast pListHead;while(--k){fast fast-next;}while(fast-next){slow slow-next; fast fast-next;}
}
三、判断链表中是否有环
给你一个链表的头节点 head 判断链表中是否有环。
使用快慢指针fast 一次走两步slow 一次走一步。
bool hasCycle(struct ListNode *head)
{ if(head NULL)return false;if(head-next NULL)return false;struct ListNode * slow head;struct ListNode * fast head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow)return true;}return false;
}
注意循环的条件是 fast ! NULL fast-next ! NULL。
四、两个单链表相交
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
要求时间复杂度O(n)空间复杂度O(1)。
思路1、分别求两个链表的长度 2、长的链表先走 差距步 3、同时走第一个地址的结点相同就是交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* tailA headA, *tailB headB; int lenA 1, lenB 1; while(tailA-next){tailA tailA-next; lenA;}while(tailB-next){tailB tailB-next; lenB;}if(tailA ! tailB)return NULL;int gap abs(lenA-lenB); struct ListNode* longList headA, *shortList headB; if(lenA ‹ lenB){longList headB; shortList headA;}while(gap--){longList longList-next;}while(longList ! shortList){longList longList-next; shortList shortList-next;}return longList;}
