160. Intersection of Two Linked Lists(Linked List-Easy)

    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.

题目：写一个程序找出两个单链表的交叉节点。
思路：单链表A和单链表B，交叉点后的部分是一样的，也就是说长度是一样的，如上所示：c1 → c2 → c3。所以，将单链表A和单链表B相差的部分去掉，依次对应比较等长的部分即可。在计算两个链表的长度之后，比较两个链表的尾节点是否一样，如果不一样说明没有交叉节点，返回NULL。

Language : c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *curA = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *curB = (struct ListNode*)malloc(sizeof(struct ListNode)); curA = headA; curB = headB; int length_a = 1; int length_b = 1; int i = 0; if(curA == NULL || curB == NULL){ return NULL; } while(curA->next != NULL){ curA = curA->next; length_a++; } while(curB->next != NULL){ curB = curB->next; length_b++; } if(curA != curB){ return NULL; } curA = headA; curB = headB; if(length_a > length_b){ for(i; i < length_a-length_b; i++){ curA = curA->next; } i = 0; } else if(length_a < length_b){ for(i; i < length_b-length_a; i++){ curB = curB->next; } i = 0; } while(curA != curB){ curA = curA->next; curB = curB->next; } return curA;
}
  

 

  
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
 

Language : cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *curA, *curB; curA = headA; curB = headB; if(curA == NULL || curB == NULL){ return NULL; } int length_a = getLength(curA); int length_b = getLength(curB); if(length_a > length_b){ for(int i=0; i < length_a-length_b; i++){ curA = curA->next; } } else if(length_a < length_b){ for(int i=0; i < length_b-length_a; i++){ curB = curB->next; } } while(curA != curB){ curA = curA->next; curB = curB->next; } return curA; }
private: int getLength(ListNode *head){ int length = 1; while(head->next != NULL){ head = head->next; length++; } return length; }
};
  

 

  
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
 

Language：python

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ if headA is None or headB is None: return None pa = headA # 2 pointers pb = headB while pa is not pb: # pa先遍历headA，然后再遍历headB # pb先遍历headB，然后再遍历headA pa = headB if pa is None else pa.next pb = headA if pb is None else pb.next return pa # 只有两种方式结束循环，一种是pa和pb所指相同，另一种是headA和headB都已经遍历完仍然没有找到。
  

 

  
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
 

文章来源: jackcui.blog.csdn.net，作者：Jack-Cui，版权归原作者所有，如需转载，请联系作者。

原文链接：jackcui.blog.csdn.net/article/details/56036016