[LeetCode][160][Intersection of Two Linked Lists ]

题目链接：https://leetcode.com/problems/intersection-of-two-linked-lists/

题目描述：

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
      

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return 

  null

  .
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

这道题首先是理解题意吧，什么是交叉节点？本题中，交叉节点是指两个链表遇到同一个节点，且从此之后的两个链表的后续节点都相同。 所以，一旦两个链表有交叉节点，那么交叉节点之后的链表长度相同，节点地址相同。 题意懂了，题就不难了，因为如果两个链表有交叉节点，那么交叉节点一定在两个链表从尾部向前数的相同位置上。 所以，先遍历两个链表的长度，计算两个链表的长度差n，用两个指针分别指向两个链表，现将长的链表的指针向后移位n个节点，然后就对比两个链表的节点是否相等即可。 代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA == NULL || headB == NULL){
        return NULL;
    }<span style="white-space:pre">				</span>//链表为空，直接返回
    struct ListNode *p,*q;
    p = headA;
    q = headB;
    int countA = 0, countB = 0;
    while(p){
        countA++;
        p = p->next;
    }<span style="white-space:pre">				</span>//遍历链表A的长度countA
    while(q){
        countB++;
        q = q->next;
    }<span style="white-space:pre">				</span>//遍历链表B的长度countB
           

int n = countA-countB;
    if (n > 0) {
        p = headA;
        q = headB;
        while(n--){
            p = p->next;
        }
    }
    else {
        p = headA;
        q = headB;
        while(n++){
            q = q->next;
        }
    }
    while(p != q){
        p = p->next;
        q = q->next;
    }<span style="white-space:pre">				</span>//如果p和q不是同一个节点，就一直遍历
    return p; <span style="white-space:pre">			</span>// p或者是交叉节点，或者为NULL
}