目录
一. 反转链表
1.思路
2.代码实现
二. 链表中倒数第k个节点
1.思路
2.代码实现
三. 相交链表
1.思路
2.代码实现
四. 环形链表
1. 思路
2. 代码实现
一. 反转链表
1.思路
2.代码实现
struct ListNode {int val;struct ListNode *next;
};//链表结构
struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;//如果为空链表，则反转后还是为空struct ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = head->next;while (n2 != NULL){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;//当n3为NULL时，不能对n3（即NULL)解引用}return n1;
}二. 链表中倒数第k个节点
1.思路
原理：slow和fast的距离拉开了k步，然后两个同时走，当fast走到空时，slow就是倒数第k个
2.代码实现
struct ListNode {int val;struct ListNode *next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{struct ListNode* fast=pListHead, * slow = pListHead;while (k--){if (fast == NULL)return NULL;//如果链表为空，或者k大于链表长度，返回空，防止对空指针的解引用fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;}return slow;
}三. 相交链表
1.思路
思路1：暴力求解
方法：A链表中所有节点依次去B链表找一遍，若有与B链表中节点地址相同的，则为相交的起始节点
时间复杂度：n^2 （因为最坏情况下，A链表的每个节点都要在B链表遍历一遍）
思路2：优化，要求时间复杂度到O(N)
方法：
1.先判断是否相交
分别找到尾节点，尾节点地址相同就相交，尾节点地址不相同就不相交
2.再分别求出A链表和B链表的长度
长的先走差距步，两个链表再同时走，第一个相同节点的地址就是交点
2.代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA=headA,*curB=headB;int lenA=1,lenB=1;while(curA->next){lenA++;curA=curA->next;}while(curB->next){lenB++;curB=curB->next;}//判断相交if(curA!=curB)return NULL;int n=abs(lenA-lenB);struct ListNode* longList=headA,*shortList=headB;if(lenB>lenA){longList=headB;shortList=headA;}//长的先走差距步while(n--){longList=longList->next;}//同时走while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;
}四. 环形链表
1. 思路
带环链：表尾节点的next可以指向链表中任意节点（甚至可以指向自己）
定义快慢指针，fast，slow，都指向头节点，slow指针一次走一步，fast指针一次走两步
若链表无环，则快慢指针不可能相遇，返回false
若链表有环，则快慢指针一定相遇，当快慢指针相遇时表示链表有环 ，返回true
2. 代码实现
struct ListNode {int val;struct ListNode *next;
};bool hasCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){return true;}}return false;
}若文章有任何问题，欢迎大家指正
