IT评测·应用市场-qidao123.com技术社区

标题: 力扣160. 相交链表 [打印本页]

---

作者: 大连密封材料    时间: 2024-6-24 06:18
标题: 力扣160. 相交链表
Problem: 160. 相交链表
  
  
题目描述

   

  思路

   用两个指针p1与p2分别指向headA与headB，当p1与p2不相当时，若p1遍历到链表A的尾部时再将p1指向headB继续遍历；若p2遍历到链表B的尾部时再将p2指向headA继续遍历；
  复杂度

时间复杂度:
                                           O                            (                            m                            +                            n                            )                                  O(m + n)                     O(m+n)；其中                                        m                                  m                     m是链表A的长度                                        n                                  n                     n是链表B的长度
  空间复杂度:
                                           O                            (                            1                            )                                  O(1)                     O(1)
  Code

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. public class Solution {
10.     /**
11.      * Find intersecting nodes of intersecting linked lists
12.      *
13.      * @param headA The head node of linked list A
14.      * @param headB The head node of linked list B
15.      * @return ListNode
16.      */
17.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
18.         ListNode p1 = headA;
19.         ListNode p2 = headB;
20.         while (p1 != p2) {
21.             if (p1 == null) {
22.                 p1 = headB;
23.             } else {
24.                 p1 = p1.next;
25.             }
26.             if (p2 == null) {
27.                 p2 = headA;
28.             } else {
29.                 p2 = p2.next;
30.             }
31.         }
32.         return p1;
33.     }
34. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4