# 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。

 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 /**   * 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;      } };

|
15天前
|

LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
10 0
|
7天前
|

[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
14 2
|
10天前
|
Java Python

11 1
|
15天前
|

LeetCode 题目 86：分隔链表
LeetCode 题目 86：分隔链表
15 2
|
15天前
|

12 1
|
15天前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
11 1
|
11天前
|

【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
9 0
|
15天前
|

LeetCode 83题：删除排序链表中的重复元素【面试】
LeetCode 83题：删除排序链表中的重复元素【面试】
5 0
|
15天前
|

LeetCode 题目 82：删除排序链表中的重复元素 II
LeetCode 题目 82：删除排序链表中的重复元素 II
10 0
|
15天前
|

LeetCode题目25 hard：K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard：K个一组翻转链表 【分治策略 Python】
17 0