leetCode 160. Intersection of Two Linked Lists 链表

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
应用型负载均衡 ALB,每月750个小时 15LCU
简介:

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;
     }
};



本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1837480

相关实践学习
部署高可用架构
本场景主要介绍如何使用云服务器ECS、负载均衡SLB、云数据库RDS和数据传输服务产品来部署多可用区高可用架构。
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
相关文章
|
15天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
7天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
14 2
|
10天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
15天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
15天前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
15天前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
11天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
15天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
15天前
|
存储 SQL 算法
LeetCode 题目 82:删除排序链表中的重复元素 II
LeetCode 题目 82:删除排序链表中的重复元素 II
|
15天前
|
算法 数据挖掘 Python
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】