💕人面只今何处去，桃花依旧笑春风💕
作者：Mylvzi
文章主要内容：详解链表OJ题
题目一：环形链表（判断链表是否带环）
题目描述：
画图分析：
代码实现：
bool hasCycle(struct ListNode *head) { struct ListNode* slow = head,*fast = head;//定义快慢指针 // 进入链表 while(fast && fast->next)//为空，就不含有环 { fast = fast->next->next; slow = slow->next; if(fast == slow)//相等，环存在 return true; } return false; }
题目二：相交链表（判断两个链表是否相交）
题目描述：
画图分析：
代码实现：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA,* curB = headB; int lenA = 1; int lenB = 1; //根据尾结点判断是否相交 // 判断尾结点是否相同 while(curA->next) { curA = curA->next; lenA++; } while(curB->next) { curB = curB->next; lenB++; } if(curA != curB)//不等于，不相交 { return NULL; } //相同，返回公共结点 int gap = abs(lenA - lenB);//得到链表长度差值 struct ListNode*longlist = headA,*shortlist = headB; if(lenA < lenB) { longlist = headB; shortlist = headA; } //先让长的链表走gap步 while(gap--) { longlist = longlist->next; } while(longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } //出循环-->走到公共结点 return longlist; }
题目三：链表分割（哨兵位使用）
题目描述：
画图分析：
代码实现：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { //创建哨兵位和两个链表 struct ListNode* lhead,* ltail;//存放比x小的 struct ListNode* ghead,* gtail;//存放比x大的 lhead = ltail =(struct ListNode*)malloc(sizeof(struct ListNode)); ghead = gtail =(struct ListNode*)malloc(sizeof(struct ListNode)); //循环遍历尾插 struct ListNode* cur = pHead; while(cur) { if(cur->val < x) { ltail->next = cur; ltail = cur; } else { gtail->next = cur; gtail = cur; } cur = cur->next; } //不置空，有可能呈环，导致死循环 gtail->next = NULL; ltail->next = ghead->next;//链接两个链表 struct ListNode* head = lhead->next; free(lhead); free(ghead); lhead = NULL; ghead = NULL; return head; } };
哨兵位总结：
“哨兵位”是一种特殊的结点，放在链表头结点之前，可以理解为工具人，就告诉你我是结点，不是NULL,但其本身不存储任何数据，为了方便对链表的链接而设置的！
出现链表链接使用哨兵位更简单，因为可以避免一种特殊的结点-->NULL,这种情况在之前往往需要单独讨论（if语句），而哨兵位的设立是我们不需要单独对这种情况讨论！
题目四：链表的回文结构（判断是否时回文链表）
题目要求：
画图分析：
代码实现：
class PalindromeList { public: //第二种写法-->头插 struct ListNode* reverseList(struct ListNode* head){ //设置新的头结点，进行头插 struct ListNode* newhead = NULL; struct ListNode* cur = head; //头插 while(cur) { struct ListNode* next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; } struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow = head,*fast = head; //开始移动 while(fast && fast->next) { fast = fast->next->next;//一次移动两步 slow = slow->next; } return slow; } bool chkPalindrome(ListNode* head) { struct ListNode* mid = middleNode(head);//得到中间结点 struct ListNode* rmid = reverseList(head);// 逆置中间结点之后的链表 while(rmid && head) { //不等于-->不是回文链表 if(rmid->val != head->val) return false; rmid = rmid->next; head = head->next; } return true; } };
题目五：环形链表II
题目要求：
2023 8 -14链表OJ（下）+
