数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在已排序的单链表中查找和为给定值的一对数 (C++)
假设我们有一个单链表和一个值 x；我们需要找到一对节点，其值的和等于 x。需要注意的是，我们不能使用额外的空间，并且期望的时间复杂度为 O(n)。
例如，如果输入是 4→7→8→9→10→11→12，x = 19，则输出将是 [(7, 12), (8, 11), (9, 10)]
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 `convert_to_xor()`，它将接收起始节点作为参数。
`prev := NULL`
当 `start` 不为 NULL 时，执行以下操作：
`next_list_node := start 的下一个节点`
`start 的下一个节点 := next_list_node 的地址与 prev 地址的异或`
`prev := start`
`start := next_list_node`
在主方法中，执行以下操作：
`first := start`
`next_list_node := NULL, prev := NULL, second := start`
当 `second` 的下一个节点不等于 `prev` 时，执行以下操作：
`temp := second`
`second := (second 的下一个节点的地址) 与 (prev 地址) 的异或`
`prev := temp`
`next_list_node := NULL`
`prev := NULL`
`flag := false`
当 (first 不等于 NULL 且 second 不等于 NULL 且 first 不等于 second 且 first 不等于 next_list_node) 时，执行以下操作：
如果 first 的数据 + second 的数据等于 x，则：
显示 first 的数据和 second 的数据
`flag := true`
`temp := first`
`first := (first 的下一个节点的地址) 与 (prev 地址) 的异或`
`prev := temp`
`temp := second`
`second := (second 的下一个节点的地址) 与 (next_list_node 地址) 的异或`
`next_list_node := temp`
否则
如果 first 的数据 + second 的数据 < x，则
`temp := first`
`first := (first 的下一个节点的地址) 与 (prev 地址) 的异或`
`prev := temp`
否则
`temp := second`
`second := (second 的下一个节点的地址) 与 (next_list_node 地址) 的异或`
`next_list_node := temp`
如果 flag 为 false，则：
没有找到这样的数对
示例 (C++)
让我们来看下面的实现，以便更好地理解：
#include<bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode *next;
ListNode(int data) {
this->data = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v) {
ListNode *start = new ListNode(v[0]);
for (int i = 1; i < v.size(); i++) {
ListNode *ptr = start;
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return start;
}
ListNode* XOR (ListNode *a, ListNode *b) {
return (ListNode*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
void convert_to_xor(ListNode *start) {
ListNode *next_list_node;
ListNode *prev = NULL;
while (start != NULL) {
next_list_node = start->next;
start->next = XOR(next_list_node, prev);
prev = start;
start = next_list_node;
}
}
void get_pared_sum(ListNode *start, int x) {
ListNode *first = start;
ListNode *next_list_node = NULL, *prev = NULL;
ListNode *second = start;
while (second->next != prev) {
ListNode *temp = second;
second = XOR(second->next, prev);
prev = temp;
}
next_list_node = NULL;
prev = NULL;
bool flag = false;
while (first != NULL && second != NULL && first != second && first != next_list_node) {
if ((first->data + second->data)==x) {
cout << "(" << first->data << ","<< second->data << ")" << endl;
flag = true;
ListNode *temp = first;
first = XOR(first->next,prev);
prev = temp;
temp = second;
second = XOR(second->next, next_list_node);
next_list_node = temp;
}
else{
if ((first->data + second->data) < x) {
ListNode *temp = first;
first = XOR(first->next,prev);
prev = temp;
}
else{
ListNode *temp = second;
second = XOR(second->next, next_list_node);
next_list_node = temp;
}
}
}
if (flag == false)
cout << "No pair found" << endl;
}
int main() {
vector<int> v = {4,7,8,9,10,11,12};
ListNode* start = make_list(v);
int x = 19;
convert_to_xor(start);
get_pared_sum(start,x);
}输入
{4,7,8,9,10,11,12}输出
(7,12) (8,11) (9,10)
110 次浏览
