160.E 相交链表

Problem: 160. 相交链表

思路

思路1：先分别计算两个链表的长度，如果长度不相等，那就让比较长的先走几步，直到两个链表长度相等。然后两个指针同步往后遍历链表，直到找到第一个相等的节点为止。

思路2：用两个新指针pA和pB先分别指向A和B的表头，在两个指针不相等的情况下，两个指针一起变化：

• 如果pA不为空，则指向pA的下一个节点，否则让pA指向B的表头

• 如果pB不为空，则指向pB的下一个节点，否则让pB指向A的表头 当pA==pB时，则找到了交点，或者两个链表都走到了表尾。

Code

代码1：

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenA, lenB := 0, 0
	for p := headA; p != nil; p = p.Next {
		lenA++
	}

	for p := headB; p != nil; p = p.Next {
		lenB++
	}

	if lenA > lenB {
		for lenA > lenB {
			headA = headA.Next
			lenA--
		}
	}

	if lenB > lenA {
		for lenB > lenA {
			headB = headB.Next
			lenB--
		}
	}

	for headA != nil {
		if headA == headB {
			return headA
		}
		headA = headA.Next
		headB = headB.Next
	}

	return nil
}

代码2：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}

	pA, pB := headA, headB
	for pA != pB {
		if pA != nil {
			pA = pA.Next
		} else {
			pA = headB
		}

		if pB != nil {
			pB = pB.Next
		} else {
			pB = headA
		}
	}

	return pA
}