LeetCode 相交链表&环形链表II

绝地灬酷狼 2023-06-04 14:51 58阅读 0赞

题目链接：[https://leetcode-cn.com/problems/intersection-of-two-linked-lists/][https_leetcode-cn.com_problems_intersection-of-two-linked-lists]

题目连接：[https://leetcode-cn.com/problems/linked-list-cycle-ii/][https_leetcode-cn.com_problems_linked-list-cycle-ii]

### 题目大意 ###

具体按左神书上的描述来实现，空间复杂度 O(1) 解决有环单链表相交问题。

### 分析 ###

关于快慢指针能找到入环节点的一些说明强烈推荐这篇博客： [https://blog.csdn.net/ffj0721/article/details/83302412][https_blog.csdn.net_ffj0721_article_details_83302412]

### 代码如下 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /**
     2  * Definition for singly-linked list.
     3  * struct ListNode {
     4  *     int val;
     5  *     ListNode *next;
     6  *     ListNode(int x) : val(x), next(NULL) {}
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    12         ListNode *loopA = detectCycle(headA), *loopB = detectCycle(headB);
    13         int lenA, lenB;
    14         
    15         if(loopA == NULL && loopB == NULL) { // 两个链表都没有环
    16             lenA = getLen(headA);
    17             lenB = getLen(headB);
    18             
    19             // 长链表先走，然后再一起走
    20             ListNode *pA = headA, *pB = headB;
    21             if(lenA > lenB) for(int i = 0; i < lenA - lenB; ++i) pA = pA->next;
    22             else for(int i = 0; i < lenB - lenA; ++i) pB = pB->next;
    23             
    24             while(pA != pB) {
    25                 pA = pA->next;
    26                 pB = pB->next;
    27             }
    28             
    29             return pA;
    30         }
    31         else if(loopA != NULL && loopB != NULL) { // 两个链表都有环
    32             if(loopA == loopB) { // 和都没有环的情况一样，只不过终点不是NULL了
    33                 lenA = getLen(headA, loopA);
    34                 lenB = getLen(headB, loopB);
    35                 
    36                 ListNode *pA = headA, *pB = headB;
    37                 if(lenA > lenB) for(int i = 0; i < lenA - lenB; ++i) pA = pA->next;
    38                 else for(int i = 0; i < lenB - lenA; ++i) pB = pB->next;
    39 
    40                 while(pA != pB) {
    41                     pA = pA->next;
    42                     pB = pB->next;
    43                 }
    44 
    45                 return pA;
    46             }
    47             else {
    48                 ListNode *p = loopA->next;
    49                 
    50                 while(p != loopA) {
    51                     if(p == loopB) return loopA; // 相交但入环点不同
    52                     p = p->next;
    53                 }
    54                 return NULL; // 不相交
    55             }
    56         }
    57         return NULL; // 一个有环一个没环，一定不相交
    58     }
    59     
    60     // 如果链表无环，返回 NULL，否则返回第一个入环节点
    61     ListNode *detectCycle(ListNode *head) {
    62         if(head == NULL || head->next == NULL || head->next->next == NULL) return NULL;
    63         
    64         ListNode *slow = head->next, *fast = head->next->next;
    65         
    66         while(fast != slow) {
    67             if(fast->next == NULL || fast->next->next == NULL) return NULL;
    68             fast = fast->next->next;
    69             slow = slow->next;
    70         }
    71         
    72         slow = head;
    73         while(fast != slow) {
    74             fast = fast->next;
    75             slow = slow->next;
    76         }
    77         
    78         return slow;
    79     }
    80     
    81     int getLen(ListNode *head, ListNode *end = NULL) {
    82         int ret = 0;
    83         while(head != end) {
    84             ++ret;
    85             head = head->next;
    86         }
    87         return ret;
    88     }
    89 };

转载于:https://www.cnblogs.com/zaq19970105/p/11350379.html

[https_leetcode-cn.com_problems_intersection-of-two-linked-lists]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[https_leetcode-cn.com_problems_linked-list-cycle-ii]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[https_blog.csdn.net_ffj0721_article_details_83302412]: https://blog.csdn.net/ffj0721/article/details/83302412
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/c5e6f55ea73247e989ab109f3801f4ed.png