p160

发表于 | 分类于 |

LeetCode p160 Intersection of Two Linked Lists 题解

1.题目：

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

题意：

输出两个链表重合的链表段的首端。
如果没有输出空

2.解题思路:

假设一段绳子，尾端是重合的。
我们每次只能移动一位找到重合的点，要想同时移动到这一位。
我们先把绳子的尾端对齐，在在开头处将长的那根绳子减去多余的长度。
因为那段多出的长度中不可能存在重合点。

3.代码

[title] [] [url] [link text]
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
 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lena = 0, lenb = 0;
		ListNode a = headA;
		ListNode b = headB;
		while (a != null) {
			lena++;
			a = a.next;
		}
		while (b != null) {
			lenb++;
			b = b.next;
		}
		if (lena > lenb) {
			int x = lena - lenb;
			for (; x > 0; x--)
				headA = headA.next;

		} else {
			int x = lenb - lena;
			for (; x > 0; x--)
				headB = headB.next;
		}
		while (headA != null && headA.val != headB.val) {
			headA = headA.next;
			headB = headB.next;

		}
		return headA;
    }
}

4.一些总结：