链表经典题目—相交链表和链表倒数第k个节点
🎉🎉🎉欢迎莅临我的博客空间，我是池央，一个对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;pcurA=headA;pcurB=headB;//链表长度int lenA=1;int lenB=1;while(pcurA->next){pcurA=pcurA->next;lenA++;}while(pcurB->next){pcurB=pcurB->next;lenB++;}//不相交,尾结点地址不同，不能用值来判断if(pcurA!=pcurB){return NULL;}//相交，找两个链表长度差，让长链表先走gap步，//两个链表在同时走,第一个相同的节点即为起始交点int gap=abs(lenA-lenB);//先假设ListNode*longList=headA;ListNode*shortList=headB;//假设不出来，再换if(lenA<lenB){longList=headB;shortList=headA;}//--gap走gap-1步while(gap--)//让长链表先走gap步{longList=longList->next;}while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;//返回相交起始节点
}链表中倒数第k个节点
代码实现
#include<stdio.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;
}