在 O(1) 时间内连接两个链表

17 Mar 2025 | 6 分钟阅读

在本教程中，我们将探讨如何在 O(1) 时间内连接两个链表。

什么是链表？

链表是一种线性数据结构，其中成员不会存储在连续的内存位置。链表的元素通过指针连接，如下图所示：

Concatenation of two Linked Lists in O(1) time

单向链表

这是最常见的链表类型。
在单向链表中，每个节点包含一些数据和一个指向下一个节点的指针。
我们必须单向移动，从头部到尾部。

双向链表

这是一种链表，可以双向移动，从头部到尾部，也可以从尾部到头部。
双向链表 (DLL) 除了下一个指针和数据外，还有一个额外的指针，有时称为前一个指针。

循环链表

循环链表是一种链表，其中所有节点都连接起来形成一个循环。
循环链表中的第一个节点和最后一个节点相互连接，形成一个圆。
因此，最后没有 NULL。

1. 对于单向链表和双向链表

给定至少每个列表都有一个指向最后一个节点的指针，可以在 O(1) 时间内连接两个列表（双向链表或单向链表）。（还有一些链接连接到列表头。）

我们以单向链表为例来检验它是如何工作的，但它也适用于双向链表。

C++ 程序

#include <iostream>
using namespace std;

class Node{

public:
	int data;
	Node* next;

	Node(int data)
	{
		this -> data = data;
		this -> next = NULL;
	}
	~Node()
	{
		int value = this -> data;

		if (this -> next != NULL){
			delete next;
			this -> next = NULL;
		}
	}
};

void insertAtTail(Node*& tail, int d)
{
	Node* temp = new Node(d);
	tail -> next = temp;
	tail = temp;
}

void print(Node*& head)
{
	Node* temp = head;

	while (temp != NULL){
		cout << temp -> data << " ";
		temp = temp -> next;
	}
	cout << endl;
}
void concat(Node*& head1, Node*& head2, Node*& tail)
{

	tail -> next = head2;
}
int main()
{
	Node* node1 = new Node(1);

	Node* head1 = node1;
	Node* tail1 = node1;

	insertAtTail(tail1, 2);
	insertAtTail(tail1, 3);
	insertAtTail(tail1, 4);
	insertAtTail(tail1, 5);

	cout << "First Linked List: " << endl;

	print(head1);

	Node* node2 = new Node(6);

	Node* head2 = node2;
	Node* tail2 = node2;

	insertAtTail(tail2, 7);
	insertAtTail(tail2, 8);
	insertAtTail(tail2, 9);
	insertAtTail(tail2, 10);

	cout << "Second Linked List: " << endl;

	print(head2);
	concat(head1, head2, tail1);

	cout << "First Linked List after concatenation: "
		<< endl;
	print(head1);

	return 0;
}

输出

First Linked List: 
1 2 3 4 5 
Second Linked List: 
6 7 8 9 10 
First Linked List after concatenation: 
1 2 3 4 5 6 7 8 9 10

Java 程序

import java.io.*;

class Node{
	int data;
	Node next;
	public Node(int data)
	{
		this.data = data;
		this.next = null;
	}
}

class JTP{

	public static Node insertAtTail(Node head1, Node tail1,
									int data)
	{
		Node temp = new Node(data);
		tail1.next = temp;
		tail1 = temp;
		return tail1;
	}

	public static void print(Node head)
	{
		Node temp = head;
		while (temp != null){
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
		System.out.println();
	}

	public static void concat(Node head1, Node head2,
							Node tail1)
	{
		tail1.next = head2;
	}

	public static void main(String[] args)
	{
		Node node1 = new Node(1);
		Node head1 = node1;
		Node tail1 = node1;

		tail1 = insertAtTail(head1, tail1, 2);
		tail1 = insertAtTail(head1, tail1, 3);
		tail1 = insertAtTail(head1, tail1, 4);
		tail1 = insertAtTail(head1, tail1, 5);

		System.out.println("First Linked List: ");
		print(head1);

		Node node2 = new Node(6);
		Node head2 = node2;
		Node tail2 = node2;

		tail2 = insertAtTail(head2, tail2, 7);
		tail2 = insertAtTail(head2, tail2, 8);
		tail2 = insertAtTail(head2, tail2, 9);
		tail2 = insertAtTail(head2, tail2, 10);

		System.out.println("Second Linked List: ");
		print(head2);

		concat(head1, head2, tail1);

		System.out.println(
			"First Linked List after concatenation: ");
		print(head1);
	}
}

输出

First Linked List: 
1 2 3 4 5 
Second Linked List: 
6 7 8 9 10 
First Linked List after concatenation: 
1 2 3 4 5 6 7 8 9 10

时间复杂度为 O(1)。

辅助空间为 O(1)。

2. 对于循环链表

我们可以简单地在 O(1) 时间内连接它们，使用循环链表。这仅仅是断开两个列表中的一个链接然后将它们连接起来。当然，这假定元素的顺序并不重要。

实施

C++ 程序

#include <bits/stdc++.h>
using namespace std;

class Node{
public:
	int data;
	Node* next;

	Node(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};

void insertNode(Node*& head, Node*& tail, int d)
{

	if (head == NULL){
		Node* newNode = new Node(d);
		head = newNode;
		tail = newNode;
		newNode->next = newNode;
	}
	else{

		Node* temp = new Node(d);
		temp->next = tail->next;
		tail->next = temp;
		tail = tail->next;
	}
}
void print(Node* head)
{
	Node* curr = head;
	if (head == NULL){
		cout << "List is Empty " << endl;
		return;
	}
	do{
		cout << curr->data << " ";
		curr = curr->next;
	} while (curr != head);
	cout << endl;
}

void concat(Node*& head1, Node*& head2)
{

	Node* temp = head1->next;
	head1->next = head2->next;
	head2->next = temp;
}

int main()
{

	Node* head1 = NULL;
	Node* tail1 = NULL;

	insertNode(head1, tail1, 1);
	insertNode(head1, tail1, 2);
	insertNode(head1, tail1, 3);
	insertNode(head1, tail1, 4);
	insertNode(head1, tail1, 5);

	Node* head2 = NULL;
	Node* tail2 = NULL;

	insertNode(head2, tail2, 6);
	insertNode(head2, tail2, 7);
	insertNode(head2, tail2, 8);
	insertNode(head2, tail2, 9);
	insertNode(head2, tail2, 10);

	cout << "Before Concatenation, First circular linked "
			"list: ";
	print(head1);

	cout << "Before Concatenation, Second circular linked "
			"list: ";
	print(head2);

	concat(head1, head2);

	cout << "After Concatenation, First circular linked "
			"list: ";
	print(head1);

	cout << "After Concatenation, Second circular linked "
			"list: ";
	print(head2);

	return 0;
}

输出

Before Concatenation, First circular linked list: 1 2 3 4 5 
Before Concatenation, Second circular linked list: 6 7 8 9 10 
After Concatenation, First circular linked list: 1 7 8 9 10 6 2 3 4 5 
After Concatenation, Second circular linked list: 6 2 3 4 5 1 7 8 9 10

Python 程序

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

def insertNode(head, tail, d):
	if head is None:
		newNode = Node(d)
		head = newNode
		tail = newNode
		newNode.next = newNode
	else:
		temp = Node(d)
		temp.next = tail.next
		tail.next = temp
		tail = tail.next
	return head, tail

def printList(head):
	curr = head
	if head is None:
		print("List is Empty")
		return
	while curr.next != head:
		print(curr.data, end=' ')
		curr = curr.next
	print(curr.data)
def concat(head1, head2):
	temp = head1.next
	head1.next = head2.next
	head2.next = temp


if __name__ == '__main__':
	head1 = None
	tail1 = None

	head1, tail1 = insertNode(head1, tail1, 1)
	head1, tail1 = insertNode(head1, tail1, 2)
	head1, tail1 = insertNode(head1, tail1, 3)
	head1, tail1 = insertNode(head1, tail1, 4)
	head1, tail1 = insertNode(head1, tail1, 5)

	head2 = None
	tail2 = None

	head2, tail2 = insertNode(head2, tail2, 6)
	head2, tail2 = insertNode(head2, tail2, 7)
	head2, tail2 = insertNode(head2, tail2, 8)
	head2, tail2 = insertNode(head2, tail2, 9)
	head2, tail2 = insertNode(head2, tail2, 10)

	print("Before Concatenation, First circular linked list: ")
	printList(head1)

	print("Before Concatenation, Second circular linked list: ")
	printList(head2)

	concat(head1, head2)

	print("After Concatenation, First circular linked list: ")
	printList(head1)

	print("After Concatenation, Second circular linked list: ")
	printList(head2)

输出

Before Concatenation, First circular linked list: 1 2 3 4 5 
Before Concatenation, Second circular linked list: 6 7 8 9 10 
After Concatenation, First circular linked list: 1 7 8 9 10 6 2 3 4 5 
After Concatenation, Second circular linked list: 6 2 3 4 5 1 7 8 9 10

时间复杂度为 O(1)。

辅助空间为 O(1)。

下一主题从给定混洗坐标形成的最小矩形面积

在 O(1) 时间内连接两个链表

什么是链表？

1. 对于单向链表和双向链表

2. 对于循环链表

联系信息

关注我们

教程

面试题

在线编译器

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

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

在 O(1) 时间内连接两个链表

什么是链表？

1. 对于单向链表和双向链表

2. 对于循环链表

相关帖子

数据结构中树和森林的区别

查找数组中左侧之和等于右侧之和的元素

二叉搜索树前序遍历的叶节点

单向链表的归并排序

DSA 中的超级鸡蛋掉落问题

围绕给定值分割链表，并且不关心使列表元素稳定

数组的平衡索引

从目标节点开始燃烧二叉树

Karger 算法用于最小割

最优二叉搜索树

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器