2016.5.24——Intersection of Two Linked Lists

Intersection of Two Linked Lists

本题收获:

1.链表的输入输出

2.交叉链表:这个链表可以有交叉点,只要前一个节点的的->next相同即可。

  题目: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.

  注意:题目中两个链表是有交叉点,只要a2,b3指向的下一个节点地址都是c1的即可。

  思路:

  我的思路:刚开把题目理解错了,以为是两个单链表有相同的节点。

  leetcode/dicuss思路:看看网上的思路

  那题目的最好解法,这技巧问题阿,遍历list1 后接着遍历list2,同时,遍历list2然后遍历list1,这样两个遍历的长度是一样的O(n+m),怎么判断相等呢?

 
  list1:    O O O O O ⑴ ⑵ ⑶
  list2:    □ □ □ □ ⑴ ⑵ ⑶
    假如list 如上,⑴ ⑵ ⑶ 为相同的节点,那么遍历list1 这样便是这样:
 
  O O O O O ⑴ ⑵ ⑶ □ □ □ □ ⑴ ⑵ ⑶
 
    遍历list2 便是这样。
 
  □  □ □ □ ⑴ ⑵ ⑶ O O O O O ⑴ ⑵ ⑶
 
  合在一起看看:
  O  O  O  O  O  ⑴  ⑵  ⑶  □   □  □  □   ⑴  ⑵  ⑶
  □   □  □   □  ⑴  ⑵  ⑶  O  O  O  O  O  ⑴  ⑵  ⑶
 
      好了,现在规律出来了。这个逻辑出来明显,主要麻烦是在遍历一个结束后接上第二个,直接改链表不好,所以,使用flag 控制。
  算法逻辑:   
  1. 判断list 是否有NULL 情况
  2. 同时遍历 两个新链表
  3. 如果节点地址相同,返回
  4. 如果不相同继续遍历
  5. 遍历结束返回NULL

  代码:

 class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA, *p2 = headB;
if(p1 == NULL || p2 == NULL)
return NULL;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
if(p1 == NULL && p2 != NULL)
p1 = headB;
if(p2 == NULL && p1 != NULL)
p2 = headA;
}
return p1;
}
};

  我的测试代码:

  代码1:是错误的理解,即两个单独的链表。 

 #include "stdafx.h"
#include "iostream"
#include "vector"
using namespace std; struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL){} //what this mean
}; class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA;
ListNode *p2 = headB; if (p1 == NULL || p2 == NULL) return NULL; while (p1 != NULL && p2 != NULL && p1 != p2) {
p1 = p1->next;
p2 = p2->next;
if (p1 == NULL) p1 = headB->next;
if (p2 == NULL) p2 = headA->next;
//cout << p1->val << endl;
//cur1 = cur1->next;
//cout << p2->val << endl;
//cur2 = cur2->next;
//cout << cur2->val << endl;
// Any time they collide or reach end together without colliding
// then return any one of the pointers.
//
if (p1->val == p2->val) //如果是两个链表找相同点,则(p1->val ==p2->val)
{
//cout << p1 << endl;
return p1;
}
//
// If one of them reaches the end earlier then reuse it
// by moving it to the beginning of other list.
// Once both of them go through reassigning,
// they will be equidistant from the collision point.
// if (p1 == NULL && p2 == NULL)
{
//cur2 = headA;
//cout << "hhh" << endl;
}
}
//cout << p1 << endl;
return p1;
}
}; int _tmain(int argc, _TCHAR* argv[])
{
ListNode *h1 = new ListNode(), *h2 = new ListNode(), *p1 = NULL, *node1 = NULL, *p2 = NULL, *node2 = NULL, *head = NULL;
vector<int> nums1 = { , , , }, nums2 = { , , , , };
//nums1 = { 1, 2, 3, 4 }; //题目理解错误,条件给的出错,
//nums2 = { 0, 9, 7, 3, 4 };
p1 = h1;
p2 = h2;
for (size_t i = ; i < nums1.size(); i++)
{
node1 = new ListNode(nums1.at(i)); if (h1 == NULL)
{
h1 = node1;
}
else p1->next = node1;
p1 = node1;
} for (size_t j = ; j < nums2.size(); j++)
{
node2 = new ListNode(nums2.at(j));
if (h2 == NULL)
{
h2 = node2;
}
else p2->next = node2;
p2 = node2;
} Solution solution;
head = solution.getIntersectionNode(h1, h2);
cout << head->val << endl; //为空所以出错
system("pause");
return ;
}

  代码2:正确思路代码,也可以看到这两的mian函数的区别。

 #include "stdafx.h"
#include "iostream"
#include "vector"
using namespace std; struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL){} //what this mean
}; /*class MyClass
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *cur1 = headA, *cur2 = headB;
//cur1 = headA, cur1 = headB;
//cout << cur1 << endl;
if (cur1 == NULL || cur2 == NULL)
return NULL; while (cur1 != cur2)
{
//cout << cur1 << endl;
cur1 = cur1->next;
//cout << cur1->val << endl;
cur2 = cur2->next;
//cout << cur2->val << endl;
if (cur1 == NULL && cur2 != NULL)
{
//cout << cur1 << endl;
cur1 = headB;
//cout << cur1->val << endl;
}
if (cur2 == NULL && cur1 != NULL)
{
cur2 = headA;
//cout << cur2->val << endl;
}
if (cur2 == NULL && cur1 == NULL) //测试是否进入空指针
{
//cur2 = headA;
cout << "hhh" << endl;
}
}
return cur1;
//cout << cur1->val << endl;
}
};*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA;
ListNode *p2 = headB; if (p1 == NULL || p2 == NULL) return NULL; while (p1 != NULL && p2 != NULL && p1 != p2) {
p1 = p1->next;
p2 = p2->next;
if (p1 == NULL) p1 = headB->next;
if (p2 == NULL) p2 = headA->next;
//cout << p1->val << endl;
//cur1 = cur1->next;
//cout << p2->val << endl;
//cur2 = cur2->next;
//cout << cur2->val << endl;
// Any time they collide or reach end together without colliding
// then return any one of the pointers.
//
if (p1 == p2) //如果是两个链表找相同点,则(p1->val ==p2->val)
{
//cout << p1 << endl;
return p1;
}
//
// If one of them reaches the end earlier then reuse it
// by moving it to the beginning of other list.
// Once both of them go through reassigning,
// they will be equidistant from the collision point.
// if (p1 == NULL && p2 == NULL)
{
//cur2 = headA;
//cout << "hhh" << endl;
}
}
//cout << p1 << endl;
return p1;
}
}; int main()
{
ListNode *head1, *head2, *node1, *node2, *node3,*node4,*node5,*head;
node1 = new ListNode(); //这样的赋值,链表就会有交叉点了,和题目一样
node2 = new ListNode();
node3 = new ListNode();
node4 = new ListNode();
node5 = new ListNode(); head1 = node1;
head1->next = node2;
node2->next = node5;
node5->next = NULL; head2 = node3;
head2->next = node4;
node4->next = node5;
node5->next = NULL; Solution solution;
head = solution.getIntersectionNode(head1, head2);
cout << head->val << endl;
system("pause");
return ;
}

  可以参见http://www.cnblogs.com/Azhu/p/4149738.html

上一篇:Ubuntu11.10与r8168网卡不兼容导致网络时断时续的问题


下一篇:2016 - 1- 21 - RunLoop使用(2016-1-24修改一次)&(2016 - 1 - 24 再次修改)