广州网站建设新际,个人做收费网站,郴州有什么好玩的地方,香橼做空机构网站#x1f389;#x1f389;#x1f389;欢迎莅临我的博客空间#xff0c;我是池央#xff0c;一个对C和数据结构怀有无限热忱的探索者。#x1f64c; #x1f338;#x1f338;#x1f338;这里是我分享C/C编程、数据结构应用的乐园✨ #x1f388;#x1f388;… 欢迎莅临我的博客空间我是池央一个对C和数据结构怀有无限热忱的探索者。 这里是我分享C/C编程、数据结构应用的乐园✨ 期待与你一同在编程的海洋中遨游探索未知的技术奥秘 专栏指路: 【C】专栏深入解析C的奥秘分享编程技巧与实践。 【数据结构】专栏探索数据结构的魅力助你提升编程能力。 本文主要介绍链表经典题目:相交链表和链表倒数第k个节点
相交链表
点击下方即可做题
相交链表
题目 画图分析 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//先找尾结点尾结点相同链表相交ListNode*pcurA,*pcurB;pcurAheadA;pcurBheadB;//链表长度int lenA1;int lenB1;while(pcurA-next){pcurApcurA-next;lenA;}while(pcurB-next){pcurBpcurB-next;lenB;}//不相交,尾结点地址不同不能用值来判断if(pcurA!pcurB){return NULL;}//相交找两个链表长度差让长链表先走gap步//两个链表在同时走,第一个相同的节点即为起始交点int gapabs(lenA-lenB);//先假设ListNode*longListheadA;ListNode*shortListheadB;//假设不出来再换if(lenAlenB){longListheadB;shortListheadA;}//--gap走gap-1步while(gap--)//让长链表先走gap步{longListlongList-next;}while(longList!shortList){longListlongList-next;shortListshortList-next;}return longList;//返回相交起始节点
}
链表中倒数第k个节点 代码实现
#includestdio.h
typedef struct ListNode ListNode;
typedef int LTDataType;
struct ListNode
{ListNode* next;LTDataType data;
};
ListNode* LTBuyNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-next NULL;newnode-data x;return newnode;
}
ListNode* RLTPos(ListNode* head, int k)//返回链表倒数第k个节点
{ListNode* fast, * slow;fast slow head;//先让fast走k步while (k--){//k还没有减到0,链表已经为空了说明k大于链表长度if (fast NULL){return NULL;}fast fast-next;}//再一起走fast走到空slow就是倒数第k个while (fast){slow slow-next;fast fast-next;}return slow;
}
int main()
{ListNode* listA1 LTBuyNode(1);ListNode* listA2 LTBuyNode(2);ListNode* listA3 LTBuyNode(3);listA1-next listA2;listA2-next listA3;listA3-next NULL;ListNode* k RLTPos(listA1, 2);printf(%d, k-data);return 0;
}
