相交鏈表

思路

鏈表交叉不可能是x型

因為有可能兩個鏈表不等長，所以我們必須讓他們從同一起跑位置去起跑

從同一起跑位置出發，依次比較每個結點的地址是否相同

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///求長度 int getLength(struct ListNode *head){int n = 0;struct ListNode *cur =head;while(cur != NULL){cur = cur->next;n++;}return n; }struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int lenA =getLength(headA);int lenB =getLength(headB);struct ListNode *longHead;struct ListNode *shortHead;int diff; //兩個鏈表的長度之差if(lenA >= lenB){longHead = headA;shortHead = headB;diff =lenA - lenB;}else{longHead = headB;shortHead = headA;diff =lenB - lenA; }for(int i = 0; i < diff; i++){ //把兩個鏈表放在同一起跑位置longHead =longHead->next;}while (longHead != shortHead){ //對結點的地址進行比較longHead =longHead->next;shortHead = shortHead->next;}return longHead; }

環形鏈表

思路

兩個指針，一個跑兩格，一個跑一格，如果快的能把滿的追上就說明有環

快指針每跑一格，都要進行判空，如果為空，就說明沒有環

還要注意初始的head就為空的情況

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ bool hasCycle(struct ListNode *head) {if(head == NULL){return false;}struct ListNode *fast = head;struct ListNode *slow = head;while(1){fast = fast->next;if(fast == NULL){return false;}fast = fast->next;if(fast == NULL){return false;}slow = slow->next;if(fast == slow){return true;}} }

返回鏈表開始入環的第一個節點

思路

/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode *detectCycle(struct ListNode *head) {if(head == NULL){return NULL;}struct ListNode *fast =head;struct ListNode *slow =head;while(1){//先找相遇點fast = fast->next;if(fast == NULL){return NULL;}fast =fast->next;if(fast == NULL){return NULL;}slow =slow->next;if(fast == slow){break;}}//一個從相遇點開始，另外一個從起始點開始，他們的相遇點就是開始入環的第一個結點struct ListNode *n1 =head;struct ListNode *n2 =slow;while( n1 != n2){n1=n1->next;n2=n2->next;} return n1; }

總結

以上是生活随笔為你收集整理的链表题目----5 相交链表 和 环形链表 和 返回链表开始入环的第一个节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。