链表求交点

59 阅读 0 评论 39 点赞

我是靠谱客的博主无奈冰棍，最近开发中收集的这篇文章主要介绍链表求交点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题来源：选自LeetCode 160. 相交链表

问题描述：　

题目给定信息：题目中给出两个链表，这两个链表有一部分节点是相互重合的，我们的目的就是要找到两个链表重合的第一个节点，这里需要注意的是链表重合，而不是两个链表的元素相同。

问题分析：

这个问题的解决思路可以由两个:

　　第一个就是利用set集合中没有重复元素的特性，先把第一个链表中的全部元素的地址（这里必须是链表节点的地址，而不是链表节点的值）都放进set集合中，然后循环遍历第二个链表，每遍历一个节点，就去判断set集合中时候存在，那么第一个在set集合中存在的元素就是两个链表相交的起始节点。然后返回这个节点就实现了该功能。

　　第二种方法就是两个链表如果从重合节点开始之后的节点都是一样的长度，但我们不能确定两个链表的长度是不是一样的，如果两个链表的长度一样，那就以链表的长度为循环次数，当两个链表部位空的时候，每遍历一个节点，就比较这两个节点时候相等（这里的相等是节点相等，不是节点的值相等），当遍历到某一个节点两个节点相等的时候证明这个节点就是重合的第一个节点，返回该节点就实现了该功能。

函数实现：

第一种方法：

 1     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 2         int headA_len = Link_len(headA);
 3         int headB_len = Link_len(headB);
 4         int move_len = (headA_len > headB_len) ? (headA_len - headB_len)
 5                 : (headB_len - headA_len);
 6         if (headA_len > headB_len) {
 7             headA = moveHead(headA, move_len);
 8         } else {
 9             headB = moveHead(headB, move_len);
10         }
11         while (headA != null && headB != null) {
12             if(headA==headB){
13                 return headA;
14             }
15             headA=headA.next;
16             headB=headB.next;
17         }
18         return null;
19     }
20     // 计算链表长度的函数
21     public int Link_len(ListNode head) {
22         int link_len = 0;
23         while (head != null) {
24             link_len++;
25             head = head.next;
26         }
27         return link_len;
28     }
29 
30     // 将某一个链表头指针向前移动指定长度的函数
31     public ListNode moveHead(ListNode head, int m) {
32         while (head != null && m != 0) {
33             head = head.next;
34             m--;
35         }
36         return head;
37     }

第二种方法：

 1  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 2         Set<ListNode> set = new HashSet<>();
 3         while (headA != null) {
 4             set.add(headA);
 5             headA = headA.next;
 6         }
 7         while (headB != null) {
 8             if(set.contains(headB)) {
 9                 return headB;
10             }
11             headB = headB.next;
12         }
13         return null;
14     }