2023 8 -14链表OJ

 

  💕人面只今何处去，桃花依旧笑春风💕

作者：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;}
};

总结：头插和尾插的区别（画图分析）