LeetCode160（相交链表）

发表于 | 分类于 ，

题目：

　　编写一个程序，找到两个单链表相交的起始节点。

思路：

　　首先需要画出示例图，方便找思路。链表问题一般需要操作很多指针，该题可以使用双指针，
但需要保持两个链表上的指针距离尾指针的距离相同。因此想到需要首先统计出两链表的长度，然后
让长链表的指针先走到和短链表的指针相同的位置。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
			return null;
		}
        ListNode node1 = headA;
        ListNode node2 = headB;
        int countA = 0;
        int countB = 0;
        while(node1 != null) {
        	countA++;
        	node1 = node1.next;
        }
        while(node2 != null) {
        	countB++;
        	node2 = node2.next;
        }
        ListNode node3 = headA;
        ListNode node4 = headB;
        if (countA > countB) {
			for(int i = 0;i < countA - countB;i++) {
				node3 = node3.next;
			}
		}else {
			for(int i = 0;i < countB - countA;i++) {
				node4 = node4.next;
			}
		}
        while(node3 != null && node4 != null) {
        	if (node3 == node4) {
				return node3;
			}
        	node3 = node3.next;
        	node4 = node4.next;
        }
        return null;
    }

复杂度分析及总结：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。