LeetCode【160.相交链表】

浅浅的花香味﹌ 2022-05-08 12:26 194阅读 0赞

### 题目描述 ###

> 编写一个程序，找到两个单链表相交的起始节点。
> 
> --------------------
> 
> 例如：  
> A: a1 → a2  
> \------------------- ↘  
> \-----------------------> c1 → c2 → c3  
> \------------------- ↗  
> B: b1 → b2 → b3
> 
> --------------------
> 
> 在节点c1开始相交。

**注意**

*  如果两个链表没有交点，返回`null`.
 *  在返回结果后，两个链表仍需要保持原有的结构。
 *  可假定整个链表结构中没有循环。

**思路 \* 1**  
将其进行两次迭代，第一次的迭代使`x = headA, y = headB` 都遍历到节点末尾，然后使`x = headB, y = headA`,接着继续遍历，如果相交的话，在接下来的遍历过程中，`x,y` 必定有相等的时刻。

**代码 \* 1**

public class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
          	ListNode x = headA, y = headB;
            while(x != y) { 
                x = x == null ? headB : x.next;
                y = y == null ? headA : y.next;
            }
            return x;     
        }
    }

**思路 \* 2**  
计算出两个链表的长度，然后比较其长度，长短不一致，则需使连个链表长度相等。

**代码 \* 2**

public class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            int lenA = getListNodelength(headA);
            int lenB = getListNodelength(headB);
            
            while(lenA > lenB) { 
                headA = headA.next;
                lenA --;
            }
            while(lenA < lenB) { 
                headB = headB.next;
                lenB --;
            }
            while(headA != headB) { 
                headA = headA.next;
                headB = headB.next;
            }
            return headA;    
        }
        public int getListNodelength(ListNode head) { 
            int length = 0;
            while(head != null) { 
                length ++;
                head = head.next;
            }
            return length;
        }
    }