首页 > 代码库 > leetcode 160

leetcode 160

2024-08-16 06:43:21   213人阅读

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.

找到两个单链表相交的点。此处假设单链表不存在环。

思路：首先获得两个单链表的长度，得到长度的差值n，然后将指向长链表的指针A先向后移动n位，之后指针A同指向短链表的指针B同时每次移动一位，当A与B指向同一节点时，该节点就是相交的结点。

 

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {12         if(headA == NULL || headB == NULL)13         {14             return NULL;15         }16         ListNode * a = headA;17         ListNode * b = headB;18         int n = 1;19         int m = 1;20         while(headA->next != NULL)21         {22             headA = headA->next;23             n++;24         }25         while(headB->next != NULL)26         {27             headB = headB->next;28             m++;29         }30         if(headA != headB)31         {32             return NULL;33         }34         if(n > m)35         {36             for(int i = 0; i < n-m; i++)37             {38                 a = a->next;39             }40             while(a)41             {42                 if(a == b)43                 {44                     return a;45                 }46                 else47                 {48                     a = a->next;49                     b = b->next;50                 }51             }52         }53         else54         {55             for(int i = 0; i < m-n; i++)56             {57                 b = b->next;58             }59             while(b)60             {61                 if(a == b)62                 {63                     return a;64                 }65                 else66                 {67                     a = a->next;68                     b = b->next;69                 }70             }71         }72         return NULL;73     }74 };

 

拓展：

http://www.cppblog.com/humanchao/archive/2015/03/22/47357.html

leetcode 160


联系
我们