Java 中两个已排序链表的交集

2024年9月10日 | 阅读10分钟

在本问题中，给定两个已排序的链表（按非递减顺序排序）。任务是找到这两个链表的交集，即找到同时存在于两个链表中的元素。

示例 1

输入

链表 1: 12 -> 13 -> 35 -> 40 -> 56 -> 89 -> 90 -> 92

链表 2: 9 -> 14 -> 15 -> 30 -> 40 -> 85 -> 90 -> 92

输出

40 -> 90 -> 92
元素 40、90 和 92 是同时存在于链表 1 和链表 2 中的共同元素。

让我们来看看解决这个问题的各种方法。

使用哑节点

该方法是在输出列表的开头使用一个哑节点或临时节点。尾指针是指向输出列表最后一个节点的指针，以便可以快速添加或追加新节点。临时节点为尾指针提供了一个可以指向的空间。请注意，最初，尾指针指向输出的哑节点。现在，任务是使用单个循环遍历给定的链表。请注意，如果任何一个链表被完全遍历，循环将终止。在循环中，使用了双指针方法。一个指针 ptr1 用于链表 1，另一个指针 ptr2 用于链表 2。有以下三种情况：

情况 1: ptr1 指向的值大于 ptr2 指向的值。

情况 2: ptr1 指向的值小于 ptr2 指向的值。

情况 3: ptr1 和 ptr2 指向的值相等。

对于情况 1，递增 ptr2 指向下一个节点。对于情况 2，递增 ptr1 指向下一个节点。对于情况 3，打印值并将两个指针都递增到指向下一个节点。在情况 3 中，我们必须处理包含相同值的节点。例如，

链表 1: 4 -> 4 -> 4 -> 4 -> 4 -> 4 -> 5

链表 2: 4 -> 4 -> 4-> 5

这里，情况 3 适用，因为两个链表的第一个节点都是 4。因此，我们打印值 4，并将 ptr1 和 ptr2 递增到指向下一个节点。然而，即使递增之后，ptr1 和 ptr2 都指向相同的值 4。因此，我们必须再次递增两个指针；但这次我们不会打印值 4，因为 4 已经打印过了，我们将继续递增指针，直到两个指针都指向值 5。

因此，输出是 4 和 5。请注意，这里的交集的工作方式与我们在“集合”章节中学习的交集的工作方式相同。

观察下面的程序。

文件名: LinkedListIntersection.java

public class LinkedListIntersection
{

// head nodes for pointing to 1st and 2nd linked lists
static LinkedLstNode p1 = null;
static LinkedLstNode p2 = null;

// a dummy or temp node for storing the intersection
static LinkedLstNode dmy = null;

// a tail node for tracking the last node of the linked
// list such that insertion of new nodes gets easy
static LinkedLstNode tl = null;

// static class LinkedLstNode
static class LinkedLstNode 
{
int val;
LinkedLstNode next;

// constructor of the class
LinkedLstNode(int v) 
{
this.val = v;
next = null;
}
}

// method for displaying the list
void displayList(LinkedLstNode st) 
{
LinkedLstNode ptr = st;
while (ptr != null) 
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}

// elements insertion in the list
void push(int v) 
{
LinkedLstNode t = new LinkedLstNode(v);
if(dmy == null) 
{
dmy = t;
tl = t;
}
else 
{
tl.next = t;
tl = t;
}
}

// method for looking for the intersection and inserting it to the dummy list
void intersectEle()
{

// pointers for iteration
LinkedLstNode ptr1 = p1;
LinkedLstNode ptr2 = p2;
int tempVal = -1;
while(ptr1 != null && ptr2 != null)
{   
if(ptr1.val == ptr2.val)
{
if(tempVal != ptr1.val)
{
// adding to the dummy list
push(ptr1.val);
tempVal = ptr1.val;
}

ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
else if(ptr1.val < ptr2.val)
{
ptr1 = ptr1.next;
}
else
ptr2 = ptr2.next;
}
}

// Driver code
public static void main(String args[])
{
// creating an object of the class LinkedListIntersection
LinkedListIntersection ll = new LinkedListIntersection();

// the first linked list
ll.p1 = new LinkedLstNode(12);
ll.p1.next = new LinkedLstNode(13);
ll.p1.next.next = new LinkedLstNode(35);
ll.p1.next.next.next = new LinkedLstNode(40);
ll.p1.next.next.next.next = new LinkedLstNode(56);
ll.p1.next.next.next.next.next = new LinkedLstNode(89);
ll.p1.next.next.next.next.next.next = new LinkedLstNode(90);
ll.p1.next.next.next.next.next.next.next = new LinkedLstNode(92);

// the second linked list
ll.p2 = new LinkedLstNode(9);
ll.p2.next = new LinkedLstNode(14);
ll.p2.next.next = new LinkedLstNode(15);
ll.p2.next.next.next = new LinkedLstNode(30);
ll.p2.next.next.next.next = new LinkedLstNode(40);
ll.p2.next.next.next.next.next = new LinkedLstNode(85);
ll.p2.next.next.next.next.next.next = new LinkedLstNode(90);
ll.p2.next.next.next.next.next.next.next = new LinkedLstNode(92);

// invoking method for call for intersection
ll.intersectEle();

// displaying the first linked list
System.out.println("The first linked list is: ");
ll.displayList(p1);

System.out.println();

// displaying the second linked list
System.out.println("The second linked list is: ");
ll.displayList(p2);

System.out.println();

// displaying the required intersection
System.out.println("The common elements of the first & the second linked list are: ");
ll.displayList(dmy);

ll.p1 = null;
ll.p2 = null;
ll.dmy = null;

ll.p1 = new LinkedLstNode(4);
ll.p1.next = new LinkedLstNode(4);
ll.p1.next.next = new LinkedLstNode(4);
ll.p1.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next.next = new LinkedLstNode(5);

ll.p2 = new LinkedLstNode(4);
ll.p2.next = new LinkedLstNode(4);
ll.p2.next.next = new LinkedLstNode(4);
ll.p2.next.next.next = new LinkedLstNode(5);


System.out.println("\n \n");

// invoking method for call for intersection
ll.intersectEle();

// displaying the first linked list
System.out.println("The first linked list is: ");
ll.displayList(p1);

System.out.println();

// displaying the second linked list
System.out.println("The second linked list is: ");
ll.displayList(p2);

System.out.println();

// displaying the required intersection
System.out.println("The common elements of the first & the second linked list are: ");
ll.displayList(dmy);

}
}

输出

The first linked list is: 
12 13 35 40 56 89 90 92 

The second linked list is: 
9 14 15 30 40 85 90 92 

The common elements of the first & the second linked list are: 
40 90 92 

 

The first linked list is: 
4 4 4 4 4 5 

The second linked list is: 
4 4 4 5 

The common elements of the first & the second linked list are: 
4 5

时间复杂度: 上述程序的 time complexity 为 O(min(a, b))，其中 a 和 b 分别是链表 1 和 2 中存在的元素或节点的数量。

使用递归

使用递归也可以实现相同的功能。

文件名: LinkedListIntersection1.java

public class LinkedListIntersection1
{

// head nodes for pointing to 1st and 2nd linked lists
static LinkedLstNode p1 = null;
static LinkedLstNode p2 = null;
static LinkedLstNode head = null;
static LinkedLstNode tail = null;

// a dummy or temp node for storing the intersection
static LinkedLstNode dmy = null;

// static class LinkedLstNode
static class LinkedLstNode 
{
int val;
LinkedLstNode next;

// constructor of the class
LinkedLstNode(int v) 
{
this.val = v;
next = null;
}
}

// method for displaying the list
void displayList(LinkedLstNode st) 
{
LinkedLstNode ptr = st;
while (ptr != null) 
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}
// method for looking for the intersection and inserting it to the dummy list
public void intersectEle(LinkedLstNode ptr1, LinkedLstNode ptr2)
{
// handling base case
if (ptr1 == null || ptr2 == null)
{
return;
}
// If both the lists are not empty 

// advancing in the list ptr1
if (ptr1.val < ptr2.val)
{
intersectEle(ptr1.next, ptr2);
}

// advancing in the list ptr2
else if (ptr1.val > ptr2.val)
{
intersectEle(ptr1, ptr2.next);
}
else 
{
// the following statements come into action
// only when ptr1.val == ptr2.val
LinkedLstNode temp = new LinkedLstNode(ptr1.val);


// Advancing both the lists using recursion
if(head == null)
{
head = temp;
tail = temp;
}

// removing the duplicates
else if(tail.val != temp.val)
{
tail.next = temp;
tail = tail.next;
}

intersectEle(ptr1.next, ptr2.next);
}
}

// Driver code
public static void main(String args[])
{
// creating an object of the class LinkedListIntersection1
LinkedListIntersection1 ll = new LinkedListIntersection1();

// the first linked list
ll.p1 = new LinkedLstNode(12);
ll.p1.next = new LinkedLstNode(13);
ll.p1.next.next = new LinkedLstNode(35);
ll.p1.next.next.next = new LinkedLstNode(40);
ll.p1.next.next.next.next = new LinkedLstNode(56);
ll.p1.next.next.next.next.next = new LinkedLstNode(89);
ll.p1.next.next.next.next.next.next = new LinkedLstNode(90);
ll.p1.next.next.next.next.next.next.next = new LinkedLstNode(92);

// the second linked list
ll.p2 = new LinkedLstNode(9);
ll.p2.next = new LinkedLstNode(14);
ll.p2.next.next = new LinkedLstNode(15);
ll.p2.next.next.next = new LinkedLstNode(30);
ll.p2.next.next.next.next = new LinkedLstNode(40);
ll.p2.next.next.next.next.next = new LinkedLstNode(85);
ll.p2.next.next.next.next.next.next = new LinkedLstNode(90);
ll.p2.next.next.next.next.next.next.next = new LinkedLstNode(92);

// invoking method for call for intersection
ll.intersectEle(ll.p1, ll.p2);

// displaying the first linked list
System.out.println("The first linked list is: ");
ll.displayList(p1);

System.out.println();

// displaying the second linked list
System.out.println("The second linked list is: ");
ll.displayList(p2);

System.out.println();

// displaying the required intersection
System.out.println("The common elements of the first & the second linked list are: ");
ll.displayList(ll.head);

ll.p1 = null;
ll.p2 = null;
ll.head = null;
ll.tail = null;

ll.p1 = new LinkedLstNode(4);
ll.p1.next = new LinkedLstNode(4);
ll.p1.next.next = new LinkedLstNode(4);
ll.p1.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next.next = new LinkedLstNode(5);

ll.p2 = new LinkedLstNode(4);
ll.p2.next = new LinkedLstNode(4);
ll.p2.next.next = new LinkedLstNode(4);
ll.p2.next.next.next = new LinkedLstNode(5);


System.out.println("\n \n");

// invoking method for call for intersection
ll.intersectEle(ll.p1, ll.p2);

// displaying the first linked list
System.out.println("The first linked list is: ");
ll.displayList(p1);

System.out.println();

// displaying the second linked list
System.out.println("The second linked list is: ");
ll.displayList(p2);

System.out.println();

// displaying the required intersection
System.out.println("The common elements of the first & the second linked list are: ");
ll.displayList(ll.head);


}
}

输出

The first linked list is: 
12 13 35 40 56 89 90 92 

The second linked list is: 
9 14 15 30 40 85 90 92 

The common elements of the first & the second linked list are: 
40 90 92

使用哈希

众所周知，Java 中的 HashSet 只包含唯一元素；因此，我们可以利用此属性来查找给定两个链表中的公共元素。观察以下程序。

文件名: LinkedListIntersection2.java

import java.util.*;

public class LinkedListIntersection2 
{
static LinkedLstNode p1 = null;
static LinkedLstNode p2 = null;

// static class LinkedLstNode
static class LinkedLstNode 
{
int val;
LinkedLstNode next;

// constructor of the class
LinkedLstNode(int v) 
{
this.val = v;
next = null;
}
}

// method for displaying the array list
public void displayList(ArrayList<Integer> aList) 
{
int size = aList.size();
for(int i = 0; i < size; i++)
{
System.out.print(aList.get(i) + " ");
}
}

// method for displaying the linked list
void displayLinkedList(LinkedLstNode st) 
{
LinkedLstNode ptr = st;
while (ptr != null) 
{
System.out.print(ptr.val + " ");
ptr = ptr.next;
}
System.out.println();
}

		
// a method for finding the common elements
public ArrayList<Integer> intersectionList(LinkedLstNode t1, LinkedLstNode t2) 
{
// common elements will be stored in this array list
ArrayList<Integer> temp = new ArrayList<Integer>();

// two hash sets for two different linked list
HashSet<Integer> set1 = new HashSet<Integer>();
HashSet<Integer> set2 = new HashSet<Integer>();

// for stroring the unique 
// elements of the linked list t1
while(t1 != null) 
{

set1.add(t1.val);
t1 = t1.next;
}


// for stroring the unique 
// elements of the linked list t2
while(t2 != null) 
{
set2.add(t2.val);
t2 = t2.next;

}

// iterating over each element 
// present in the set 1
for (Integer i : set1) 
{
if(set2.contains(i))
{
    // reaching here means
    // integer i is present in
    // both the sets and therefore
    // we can add it in the array list
    temp.add(i);
}
    
}

return temp;

}
	
	
public static void main(String[] args) 
{
// creating an object of the class LinkedListIntersection2
LinkedListIntersection2 ll = new LinkedListIntersection2();

// the first linked list
ll.p1 = new LinkedLstNode(12);
ll.p1.next = new LinkedLstNode(13);
ll.p1.next.next = new LinkedLstNode(35);
ll.p1.next.next.next = new LinkedLstNode(40);
ll.p1.next.next.next.next = new LinkedLstNode(56);
ll.p1.next.next.next.next.next = new LinkedLstNode(89);
ll.p1.next.next.next.next.next.next = new LinkedLstNode(90);
ll.p1.next.next.next.next.next.next.next = new LinkedLstNode(92);

// the second linked list
ll.p2 = new LinkedLstNode(9);
ll.p2.next = new LinkedLstNode(14);
ll.p2.next.next = new LinkedLstNode(15);
ll.p2.next.next.next = new LinkedLstNode(30);
ll.p2.next.next.next.next = new LinkedLstNode(40);
ll.p2.next.next.next.next.next = new LinkedLstNode(85);
ll.p2.next.next.next.next.next.next = new LinkedLstNode(90);
ll.p2.next.next.next.next.next.next.next = new LinkedLstNode(92);

// displaying the first linked list
System.out.println("The first linked list is: ");
ll.displayLinkedList(p1);

System.out.println();

// displaying the second linked list
System.out.println("The second linked list is: ");
ll.displayLinkedList(p2);

System.out.println();

ArrayList<Integer> al = ll.intersectionList(ll.p1, ll.p2);

System.out.println("The common elements of the first & the second linked list are: ");
ll.displayList(al);

ll.p1 = null;
ll.p2 = null;

ll.p1 = new LinkedLstNode(4);
ll.p1.next = new LinkedLstNode(4);
ll.p1.next.next = new LinkedLstNode(4);
ll.p1.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next = new LinkedLstNode(4);
ll.p1.next.next.next.next.next = new LinkedLstNode(5);

ll.p2 = new LinkedLstNode(4);
ll.p2.next = new LinkedLstNode(4);
ll.p2.next.next = new LinkedLstNode(4);
ll.p2.next.next.next = new LinkedLstNode(5);


System.out.println("\n \n");

al = ll.intersectionList(ll.p1, ll.p2);

// displaying the first linked list
System.out.println("The first linked list is: ");
ll.displayLinkedList(p1);

System.out.println();

// displaying the second linked list
System.out.println("The second linked list is: ");
ll.displayLinkedList(p2);

System.out.println();

System.out.println("The common elements of the first & the second linked list are: ");
ll.displayList(al);

}

}

输出

The first linked list is: 
12 13 35 40 56 89 90 92 

The second linked list is: 
9 14 15 30 40 85 90 92 

The common elements of the first & the second linked list are: 
40 90 92

时间复杂度: 由于我们分别遍历两个链表，因此上述程序的 time complexity 为 O(a + b)，其中 a 和 b 是给定链表中存在的节点总数。

下一个主题Java 中的设置矩阵零

Java 中两个已排序链表的交集

使用哑节点

使用递归

使用哈希

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中两个已排序链表的交集

使用哑节点

使用递归

使用哈希

相关帖子

Java BigDecimal toString()

How to Solve Time Limit Exceeded Problem in Java?

How to Achieve Multiple Inheritance in Java

Java 中静态函数的阴影

Java 11 Lambda 表达式中的 var

Passing Strings By Reference in Java

Java 中的图像处理 - 创建随机像素图像

Java 中一些棘手的程序

Java 中早期绑定和晚期绑定的区别

Java 中的服务器套接字

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器