leetCode 160. Intersection of Two Linked Lists 链表

160. 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.

题目大意：

找出两个链表后半部分的交汇点。

思路：

1.求出两个链表的长度。

2.获取链表长度差n。

3.将长的链表先移动到第n个节点。

4.对长链表和短链表进行比较。(同时向后移动)如果在链表尾之前找到相等的节点，返回该节点，如果没找到，返回NULL。

代码如下：

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     int listLength(ListNode *head)//用快指针求链表长度     {         ListNode * p = head;         int i = 0 ;         while(p && p->next)         {             i++;             p = p->next->next;         }         if(p == NULL)             return 2 * i;         return 2 * i + 1;     }     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {         int lenA = listLength(headA);         int lenB = listLength(headB);                  int maxLen = lenA > lenB ? lenA :lenB;         int remain ;          ListNode * la,*lb;         la = headA;         lb = headB;                  if(maxLen == lenA)         {             remain = lenA - lenB;             while(remain--)             {                 la = la->next;             }         }         else         {             remain = lenB - lenA;             while(remain--)                 lb = lb->next;         }                  while(lb != NULL)         {             if(la != lb)             {                 la = la->next;                 lb = lb->next;             }             else             {                 return la;             }         }         return NULL;     } };

2016-08-13 01:08:14