如果您想了解[Leetcode题目]160.IntersectionofTwoLinkedLists和leetcode例题的知识，那么本篇文章将是您的不二之选。我们将深入剖析[Leetcode题目]1

如果您想了解[Leetcode题目]160. Intersection of Two Linked Lists和leetcode例题的知识，那么本篇文章将是您的不二之选。我们将深入剖析[Leetcode题目]160. Intersection of Two Linked Lists的各个方面，并为您解答leetcode例题的疑在这篇文章中，我们将为您介绍[Leetcode题目]160. Intersection of Two Linked Lists的相关知识，同时也会详细的解释leetcode例题的运用方法，并给出实际的案例分析，希望能帮助到您！

• [Leetcode题目]160. Intersection of Two Linked Lists（leetcode例题）
• 160. Intersection of Two Linked Lists
• 169.Intersection of Two Linked Lists（两个链表的交集）
• Intersection of Two Linked Lists
• LeetCode - Easy - 350. Intersection of Two Arrays II

[Leetcode题目]160. Intersection of Two Linked Lists（leetcode例题）

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，如果没有共同部分，返回null

思路：

计算出a和b的长度，截取掉较长的链表多出来的开头部分，然后再同时向后，当节点相同时即共同部分的起点。

/**
 * 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) {
        if(headA==null||headB==null){
            return null;
        }
        
        //算出链表长度，并截取较长的链表
        int lenA=getLength(headA);
        int lenB=getLength(headB);
        if(lenA>lenB){
            headA=goLength(headA,lenA-lenB);
        }
        else if(lenA<lenB){
            headB=goLength(headB,lenB-lenA);
        }
        
        //链表长度相等，由此向后一一比较
        while(headA!=null){
            if(headA==headB){
                return headA;
            }
            else{
                headA=headA.next;
                headB=headB.next;
            }
        }
        return null;
    }
    
    //获得链表长度
    public int getLength(ListNode node){
        int length=0;
        while(node!=null){
            node=node.next;
            length++;
        }
        return length;
    }
    //从表头向后n个节点
    public ListNode goLength(ListNode node,int length){
        for(int i=0;i<length;i++){
            node=node.next;
        }
        return node;
    }
}

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.

解答：

public class Solution {
    //非常聪明的解法，因为两个linkedlist的长度不一样，所以它让两个指针通过两次循环，
    //来把两个linkedlist都扫一遍。因为公共的部分相同，所以当它们相遇的时候，就是intersection。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        ListNode a = headA;
        ListNode b = headB;
        
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        
        return a;
    }
}

169.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.

开始在节点c1处相交。

Notes:

• If the two linked lists have no intersection at all, return null.如果两个链接列表根本没有交集，则返回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.您的代码最好在O（n）时间内运行，并且只使用O（1）内存。

解答：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
14         if(headA==null || headB==null) return null;
15         ListNode a=headA,b=headB;
16         while(a!=b){
17             a=(a!=null) ? a.next:headB;
18             b=(b!=null) ? b.next:headA;
19         }
20         return a;
21     }
22 }

详解：

分别用两个指针指向两个链表的开头，当其中一条遍历到末尾时，跳到另一条链表继续遍历，两个指针最终会相等。

要么在交点处相遇，要么在各自末尾空节点处。如果没有交点，两个指针走过的路径长度都是两个链表长度之和；如果有交点，交点后的长度相等，总长度也相等，所以交点前的长度也相等。

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.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

/**
 * 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 la = getListNodeLength(headA);
        int lb = getListNodeLength(headB);
        int dif = la < lb ? lb - la : la - lb;
		
        if (la < lb) {
            for (int i = 0; i < dif; ++ i) {
                headB = headB.next;
            }
        }
        else {
            for (int i = 0; i < dif; ++ i) {
                headA = headA.next;
            }
        }
		
        while (null != headA) {
            if (headA.val == headB.val) return headA;
            headA = headA.next;
            headB = headB.next;
        }
		
        return null;
    }
    
    public static int getListNodeLength(ListNode ln) {
        int len = 0;
		
        for (; null != ln; ln = ln.next) {
            len += 1;
        }
		
        return len;
    }
}

LeetCode - Easy - 350. Intersection of Two Arrays II

Topic

• Hash Table
• Two Pointers
• Binary Search
• Sort

Description

https://leetcode.com/problems/intersection-of-two-arrays-ii/

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1''s size is small compared to nums2''s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Analysis

方法一：我写的。

方法二：别人写的，与方法一思路一致，代码简洁些。

方法三：排序两数组，然后用两指针齐齐比较得出结果。

方法四：Java8 式写法。

Submission

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class IntersectionOfTwoArraysII {

	// 方法一：我写的
	public int[] intersect1(int[] nums1, int[] nums2) {
		if (nums1 == null || nums2 == null || //
				nums1.length == 0 || nums2.length == 0)
			return new int[] {};

		if (nums1.length > nums2.length) {// 这if语块可省略
			int[] temp = nums1;
			nums1 = nums2;
			nums2 = temp;
		}

		Map<Integer, Integer> num2count = new HashMap<>();

		for (int n : nums1) {
			Integer count = num2count.get(n);
			if (count == null)
				count = 0;
			num2count.put(n, count + 1);
		}

		List<Integer> list = new ArrayList<>();
		for (int n : nums2) {
			Integer count = num2count.get(n);
			if (count != null && count > 0) {
				list.add(n);
				num2count.put(n, count - 1);
			}
		}
		int[] result = new int[list.size()];

		for (int i = 0; i < list.size(); i++)
			result[i] = list.get(i);

		return result;
	}

	// 方法二：别人写的，与方法一思路一致，代码简洁些
	public int[] intersect2(int[] nums1, int[] nums2) {
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i : nums1)
			map.put(i, map.getOrDefault(i, 0) + 1);

		ArrayList<Integer> list = new ArrayList<>();
		for (int i : nums2) {
			if (map.get(i) != null && map.get(i) > 0) {
				list.add(i);
				map.put(i, map.get(i) - 1);
			}
		}
		int[] ret = new int[list.size()];
		for (int i = 0; i < list.size(); i++) {
			ret[i] = list.get(i);
		}
		return ret;
	}

	// 方法三：排序两数组，然后齐齐
	public int[] intersect3(int[] nums1, int[] nums2) {
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		int n = nums1.length, m = nums2.length;
		int i = 0, j = 0;
		List<Integer> list = new ArrayList<>();
		while (i < n && j < m) {
			int a = nums1[i], b = nums2[j];
			if (a == b) {
				list.add(a);
				i++;
				j++;
			} else if (a < b) {
				i++;
			} else {
				j++;
			}
		}
		int[] ret = new int[list.size()];
		for (int k = 0; k < list.size(); k++)
			ret[k] = list.get(k);
		return ret;
	}

	// 方法四：Java8版
	public int[] intersect4(int[] nums1, int[] nums2) {
		Map<Integer, Long> map = Arrays.stream(nums2).boxed()
				.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
		return Arrays.stream(nums1).filter(e -> {
			if (!map.containsKey(e))
				return false;
			map.put(e, map.get(e) - 1);
			if (map.get(e) == 0)
				map.remove(e);
			return true;
		}).toArray();
	}

}

Test

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class IntersectionOfTwoArraysIITest {

	@Test
	public void test1() {
		IntersectionOfTwoArraysII obj = new IntersectionOfTwoArraysII();

		int[] array1 = { 1, 2, 2, 1 };
		int[] array2 = { 2, 2 };

		assertArrayEquals(array2, obj.intersect1(array1, array2));
		assertArrayEquals(array2, obj.intersect2(array1, array2));
		assertArrayEquals(array2, obj.intersect3(array1, array2));
		assertArrayEquals(array2, obj.intersect4(array1, array2));
	}

	@Test
	public void test2() {
		IntersectionOfTwoArraysII obj = new IntersectionOfTwoArraysII();

		int[] array1 = { 4, 9, 5 };
		int[] array2 = { 9, 4, 9, 8, 4 };
		int[] expected = { 9, 4 }, actual;
		Arrays.sort(expected);

		actual = obj.intersect1(array1, array2);
		Arrays.sort(actual);
		assertArrayEquals(expected, actual);

		actual = obj.intersect2(array1, array2);
		Arrays.sort(actual);
		assertArrayEquals(expected, actual);

		actual = obj.intersect3(array1, array2);
		Arrays.sort(actual);
		assertArrayEquals(expected, actual);

		actual = obj.intersect4(array1, array2);
		Arrays.sort(actual);
		assertArrayEquals(expected, actual);

	}
}

今天关于[Leetcode题目]160. Intersection of Two Linked Lists和leetcode例题的讲解已经结束，谢谢您的阅读，如果想了解更多关于160. Intersection of Two Linked Lists、169.Intersection of Two Linked Lists（两个链表的交集）、Intersection of Two Linked Lists、LeetCode - Easy - 350. Intersection of Two Arrays II的相关知识，请在本站搜索。