常见队列栈链表面试题目及C++实现
程序员文章站
2022-05-06 11:05:47
...
文章目录
- 1 只使用一个数组，实现大小固定的栈和队列
- 2.实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
- 3 如何仅用队列结构实现栈结构？ 如何仅用栈结构实现队列结构？
- 4 猫狗队列 【题目】 宠物、狗和猫的类如下：
- 5. 转圈打印矩阵
- 6 一个正方形N*N，顺时针转90度，如何？ 【咦，不是矩阵转置吗】
- 7 反转单向和双向链表
- 8.“之”字形打印矩阵
- 9 在行列都排好序的矩阵中找数
- 10 打印两个有序链表的公共部分
- 11.判断一个链表是否为回文结构
- 12.将单向链表按某值划分成左边小、中间相等、右边大的形式
- 13.复制含有随机指针节点的链表
- 14.两个单链表相交的一系列问题
1 只使用一个数组，实现大小固定的栈和队列
数组实现栈：
引入全局Index 的设计，出去一个数Index – ，进来一个数Index ++ 【代码很短，面试题目可能会有】
数组实现队列：
引入start，end 全局变量指向数组的头和尾，push和pop的时候可以直接根据两个变量操作。同时引入全局size变量，帮助确定是否可以push和pop。另外，对于一个数组start，end在进行入队出队的时候会出现与数组坐标不协调但是数组并没有用完的情况，所以如果两个指针指向数组尾的时候就重新指向数组头0，循环利用。
class Stack
{
public:
int* arrayStack;
int stacksize;
int length;
Stack(int initSize)
{
if(initSize < 0)
cout<<"The init size is less than 0."<<endl;
arrayStack = new int[initSize];
stacksize = 0;
length = initSize;
}
//返回队列头部的元素
int peep()
{
if(stacksize == 0)
return NULL;
return arrayStack[stacksize-1];
}
void push(int obj)
{
if(stacksize == length)
cout<<"The Stack is full!"<<endl;
arrayStack[stacksize++] = obj;
}
int pop()
{
if(stacksize <= 0)
cout<<"The Stack is empty!"<<endl;
return arrayStack[stacksize--];
}
bool isEmpty()
{
return (bool)stacksize;
}
};
class Queue
{
public:
int start;
int ended;
int * arrayQueue;
int queueSize;
int length;
Queue(int initSize)
{
if(initSize < 0)
cout << "The init size is less than 0."<< endl;
arrayQueue = new int[initSize];
queueSize = 0;
start = 0;
ended = 0;
length = initSize;
}
//返回队列首元素
int peek()
{
if(queueSize == 0)
cout <<"The Queue is empty."<<endl;
return arrayQueue[start];
}
void push(int obj)
{
if(queueSize == length)
cout<<"The Queue is full."<<endl;
arrayQueue[ended] = obj;
queueSize++;
if(ended == length-1)
ended = 0;
else
ended++;
}
int pop ()
{
if(queueSize == 0)
cout<<"The Queue is empty."<<endl;
int temp = arrayQueue[start];
if(start == length-1)
start = 0;
else
start++;
return temp;
}
};
2.实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】 1．pop、push、getMin操作的时间复杂度都是O(1)。
2．设计的栈类型可以使用现成的栈结构。
思路：
设计两个栈，一个data栈,一个min栈，data栈就是正常的入栈出战操作，而min栈在入栈的时候，每次压入的是当前最小的元素，如果新进入的值比栈顶小那么直接压入栈中，如果不小，那么压入一个栈顶元素的值，这样出栈的时候【两个栈同时弹出】，每次都可以获得当前最小的值。
#include <iostream>
#include <stack>
class getMinStack
{
public:
stack<int> data;
stack<int> Min;
void push(int obj)
{
if(Min.empty())
{
Min.push(obj);
}
else if(obj <= Min.top())
{
Min.push(obj);
}else
{
Min.push(Min.top());
}
data.push(obj);
}
int pop()
{
if(data.empty())
cout<<"The stack is empty!"<<endl;
Min.pop();
int temp = data.top();
data.pop();
return temp;
}
int getMin()
{
if(Min.empty())
cout<<"The stack is empty!"<<endl;
return Min.top();
}
void printStack(stack<int> s)
{
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
cout<<endl;
}
};
int main()
{
cout << "Hello world!" << endl;
getMinStack gs;
gs.push(9);
gs.push(7);
gs.push(10);
gs.push(7);
cout<<gs.getMin()<<endl;;
gs.printStack(gs.data);
gs.printStack(gs.Min);
return 0;
}
3 如何仅用队列结构实现栈结构？ 如何仅用栈结构实现队列结构？
面试题：【图的深度优先遍历是用栈实现的，但是面试官让使用队列实现图的深度优先遍历，这时可以用两个队列实现栈，然后再实现深度优先遍历】
所以这两个题目思路一样：
仅用队列结构实现栈结构
准备队列两个 【队列是先进先出】
一个Data ，一个help，进队列的时候数据只进入data队列，出的时候，因为要实现栈，出的时候要先出最先进入的那个，这时如果data中不只一个数，那么data中的数导入help中，直到只剩下一个数，取出，这时data和help的相对关系改变。
class twoQueuesStack
{
public:
queue<int> data;
queue<int> help;
void push(int obj)
{
data.push(obj);
}
void Swap()
{
queue<int> tmp =data;
data = help;
help = tmp;
}
int pop()
{
if(data.empty())
cout<<"The Stack is empty!"<<endl;
while(data.size()>1)
{
int temp = data.front();
data.pop();
help.push(temp);
}
int res = data.front();
data.pop();
Swap();
return res;
}
int top()
{
if(data.empty())
cout<<"The Stack is empty!"<<endl;
while(data.size()>1)
{
int temp = data.front();
data.pop();
help.push(temp);
}
int res = data.front();
help.push(res);
data.pop();
Swap();
return res;
}
printStack(queue<int> data)
{
while(!data.empty())
{
cout<<data.front()<<" ";
data.pop();
}
cout<<endl;
}
};
int main()
{
cout << "Hello world!" << endl;
twoQueuesStack s;
int i=0;
while(i<10)
{
s.push(i);
i++;
}
s.printStack(s.data);
cout<<"top: "<<s.top()<<endl;
s.pop();
cout<<"top: "<<s.top()<<endl;
s.push(12);
cout<<"top: "<<s.top()<<endl;
return 0;
}
仅用栈结构实现队列结构
准备栈两个【栈是先进后出】
一个用来Push，一个用来pop，数据只进入push栈，取数据的时候，数据全部导入pop栈中，如果pop中有数据则不可以转入数据。
class twoStacksQueue
{
public:
stack<int> stackPush;
stack<int> stackPop;
void push(int obj)
{
stackPush.push(obj);
}
int pop()
{
if(stackPush.empty() && stackPop.empty())
cout<<"The stack is empty!"<<endl;
else if(stackPop.empty())
{
while(!stackPush.empty())
{
int temp = stackPush.top();
stackPush.pop();
stackPop.push(temp);
}
}
int res = stackPop.top();
stackPop.pop();
return res;
}
int top()
{
if(stackPush.empty() && stackPop.empty())
cout<<"The stack is empty!"<<endl;
else if(stackPop.empty())
{
while(!stackPush.empty())
{
int temp = stackPush.top();
stackPush.pop();
stackPop.push(temp);
}
}
int res = stackPop.top();
return res;
}
};
4 猫狗队列 【题目】 宠物、狗和猫的类如下：
public class Pet {
private String type;
public Pet(String type) { this.type = type; }
public String getPetType() { return this.type; } }
public class Dog extends Pet { public Dog() { super("dog"); } }
public class Cat extends Pet { public Cat() { super("cat"); } }
实现一种狗猫队列的结构，要求如下：
用户可以调用add方法将cat类或dog类的 实例放入队列中；
用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
用户可以调用pollDog方法，将队列中dog类的实例按照 进队列的先后顺序依次弹出；
用户可以调用pollCat方法，将队列中cat类的实 例按照进队列的先后顺序依次弹出；
用户可以调用isEmpty方法，检查队列中是 否还有dog或cat的实例；
用户可以调用isDogEmpty方法，检查队列中是否有dog 类的实例；
用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。
本题考查实现特殊数据结构的能力以及针对特殊功能的算法设计能力。
本题为开放类型的面试题,希望读者能有自己的实现,在这里列出几种常见的设计错误:
-
cat队列只放cat实例,dog队列只放dog实例,再用一个总队列放所有的实例。错误原因:cat、dog以及总队列的更新问题。
-
用哈希表,key表示个ca实例或dog实例,vaue表示这个实例进队列的次序。错误原因:不能支持一个实例多次进队列的功能需求因为哈希表的key只能对应—个value值。
-
将用户原有的ca或dog类改写,加个计数项来表示某一个实例进队列的时间。错误原因:不能擅自改变用户的类结构。
本题实现将不同的实例盖上时间戳的方法,但是又不能改变用户本身的类,所以定义一个新的类PetEnterQueue
大体说来,首先有一个不断累加的数据项,用来表示实例进队列的时间;同时有两个队列,一个是只放dog类实例的队列dogQ,另一个是只放cat类实例的队列catQ。
在加入实例时,如果实例是dog,盖上时间戳,生成对应的Petenterqueue类的实例,然后放入dogQ;如果实例是cat,就盖上时间戳,生成对应的 Petenterqueue类的实例,然后放入catQ。
5. 转圈打印矩阵
【题目】 给定一个整型矩阵matrix，请按照转圈的方式打印它。 例如：[[ 1 2 3 4] [5 6 7 8] [ 9 10 11 12] [13 14 15 16 ] ]打印结果为：1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10
【要求】 额外空间复杂度为O(1)。
思路：如果考虑打印的时候变换坐标是很麻烦的，因此考虑能不能从宏观的角度分析矩阵，如果给定左上和右下的坐标就可以构成一个圈，这时就可以分圈的形式打印矩阵。
#include <iostream>
#include <vector>
using namespace std;
void printEdge(vector<vector<int>> const arr,int a,int b,int c,int d);
void spiralOrderPrint(vector<vector<int>> arr)
{
if(arr.size() == 0)
return;
int a =0;
int b = 0;
int c = arr.size()-1;
int d = arr[0].size()-1;
while(a <= c && b <= d )
printEdge(arr,a++,b++,c--,d--);
cout<<endl;
}
void printEdge(vector<vector<int>> const arr,int a,int b,int c,int d)
{
if(a == c)
{
//列比行多，一定是从左向右遍历最后一行
for(int i = b; i<=d;i++)
cout<< arr[a][i]<<" ";
}
else if(b == d)
{
//行比列多，一定是从上向下遍历最后一列
for(int j = a;j<=c;j++)
cout<< arr[j][b]<<" ";
}
else
{
for(int i = b;i < d;i++)
cout<< arr[a][i]<<" ";
for(int i = a;i < c;i++)
cout<< arr[i][d]<<" ";
for(int i = d;i > b;i--)
cout<< arr[c][i]<<" ";
for(int i = c;i > a;i--)
cout<< arr[i][b]<<" ";
}
}
void printMatrix(const vector<vector<int>> arr)
{
for(int i=0;i<arr.size();i++)
{
for(int j=0;j<arr[0].size();j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}
}
int main()
{
cout << "Hello world!" << endl;
vector<vector<int>> arr = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
vector<vector<int>> arr2 = {{1,2,3,4,22},{5,6,7,8,33},{9,10,11,12,44},{13,14,15,16,55}};
spiralOrderPrint(arr);
printMatrix(arr2);
spiralOrderPrint(arr2);
return 0;
}
6 一个正方形N*N，顺时针转90度，如何？ 【咦，不是矩阵转置吗】
不可以准备数组，不申请额外空间。
可以用分圈结构来做，先转外圈，再往里走。因为是旋转一个正方形矩阵，所以找到对应的要换位置的四个点即可，对应关系如下，实现的时候用一个变量times替代m,n,q即可。
#include <iostream>
#include<vector>
using namespace std;
void rotateEdge(vector<vector<int>> &matrix, int a, int b, int c, int d);
void rotate(vector<vector<int>> &matrix)
{
int tR = 0;
int tC = 0;
int dR = matrix.size()- 1;
int dC = matrix[0].size() - 1;
while (tR < dR) {
rotateEdge(matrix, tR++, tC++, dR--, dC--);
}
}
void rotateEdge(vector<vector<int>> &matrix, int a, int b, int c, int d)
{
int times = d - b;
int tmp = 0;
for (int i = 0; i != times; i++) {
tmp = matrix[a][b + i];
matrix[a][b + i] = matrix[c - i][b];
matrix[c - i][b] = matrix[c][d - i];
matrix[c][d - i] = matrix[a + i][d];
matrix[a + i][d] = tmp;
}
}
void printMatrix(const vector<vector<int>> arr)
{
for(int i=0;i<arr.size();i++)
{
for(int j=0;j<arr[0].size();j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}
}
int main()
{
cout << "Hello world!" << endl;
vector<vector<int>> arr = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
printMatrix(arr);
cout<<"rotate matrix!"<<endl;
rotate(arr);
printMatrix(arr);
return 0;
}
7 反转单向和双向链表
【题目】 分别实现反转单向链表和反转双向链表的函数。
【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)
class linkList
{
public:
struct singleNode{
int value;
singleNode* next;
};
struct doubleNode{
int value;
doubleNode* pre;
doubleNode* next;
};
singleNode* reverseSingleNode(singleNode* head)
{
singleNode *pre = nullptr;
singleNode *next = nullptr;
//head为当前，pre为之前，next为之后
while(nullptr != head)
{
next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
doubleNode* reverseDoubleNode(doubleNode* head)
{
doubleNode *pre;
doubleNode *next;
while(head != nullptr)
{
next = head->next;
head->next = pre;
head->pre = next;
pre = head;
head = next;
}
return pre;
}
void printList(singleNode *head)
{
while(nullptr != head)
{
cout << head->value << " ";
head = head->next;
}
cout << endl;
}
void printList(doubleNode *head)
{
while(nullptr != head)
{
cout << head->value << " ";
head = head->next;
}
cout << endl;
}
};
8.“之”字形打印矩阵
【题目】 给定一个矩阵matrix，按照“之”字形的方式打印这 个矩阵，例如： 1 2 3 4 5 6 7 8 9 10 11 12 “之”字形打印的结果为：1，2，5，9，6，3，4，7，10，11， 8，12
【要求】 额外空间复杂度为O(1)。
设计宏观方法：首先设计两个点AB，都指向矩阵的左上角，
然后A 向右走，如果走到最后向下，B向下走，如果走到最后向右
这样每次都可以画出对角线，但是还需要直到每条对角线上的数按照从右上打到左下，还是从左下打到右上，所以可以设置一个bool值，每打印一次改变一次。
void ZigPrintMatrix(vector<vector<int>> arr)
{
if(arr.size() == 0)
return ;
bool flag = true;
int topRow = 0;
int topCol = 0;
int downRow = 0;
int downCol = 0;
int endRow = arr.size() - 1;
int endCol = arr[0].size() - 1;
bool fromUp = false;
while (topRow != endRow + 1) {
printDiag(arr, topRow, topCol, downRow, downCol, fromUp);
topRow = topCol == endCol ? topRow + 1 : topRow;
topCol = topCol == endCol ? topCol : topCol + 1;
downCol = downRow == endRow ? downCol + 1 : downCol;
downRow = downRow == endRow ? downRow : downRow + 1;
fromUp = !fromUp;
}
cout<<endl;
}
void printDiag(vector<vector<int>> arr,int topRow,int topCol,int downRow,int downCol,bool flag)
{
if (flag)
{
while (topRow != downRow + 1) {
cout<<arr[topRow++][topCol--] << " ";
}
} else {
while (downRow != topRow - 1) {
cout<<arr[downRow--][downCol++] << " ";
}
}
}
9 在行列都排好序的矩阵中找数
【题目】 给定一个有N*M的整型矩阵matrix和一个整数K， matrix的每一行和每一 列都是排好序的。实现一个函数，判断K 是否在matrix中。 例如： 0 1 2 5 2 3 4 7 4 4 4 8 5 7 7 9 如果K为7，返回true；如果K为6，返 回false。
【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)。
从右上开始遍历，如果大于K，则该列都大于K，删除该列，向左移动，如果小于K，则这一行都不可能有K，删去该行，向下移动，重复该过程直到找到K或者遍历结束。
或者，从左下开始遍历，是一样的，只是逻辑稍微不同。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int rows = array.size();
int colums = array[0].size();
if(rows <= 0 || colums <= 0 )
return false;
int colum = 0;
int row = rows-1;
while(row >= 0 && colum < colums)
{
if(array[row][colum] < target)
{
colum++;
}
else if(array[row][colum] > target)
{
row--;
}
else if(array[row][colum] == target)
{
return true;
}
else
{
return false;
}
}
return false;
}
};
10 打印两个有序链表的公共部分
【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
因为是有序链表，所有两个链表的头开始如下判断
- 如果head1的值小于head2,则head1向下移动
- 如果head1的值大于head2,则head2向下移动
- 如果head1等于haed2，则打印这个值，然后head1和head2都向下移动
【给出的Java代码没有修改】
public static void PrintPublicValue(Node head1,Node head2) {
while(head1 != null && head2 != null) {
if(head1.value < head2.value) {
head1 = head1.next;
}else if(head1.value > head2.value) {
head2 = head2.next;
}else {
System.out.println(head1.value);
head1 = head1.next;
head2 = head2.next;
}
}
11.判断一个链表是否为回文结构
【题目】 给定一个链表的头节点head，请判断该链表是否为回 文结构。
例如： 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返
回false。
进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。
可以使用额外空间：
- 遍历的过程中，将节点放在栈中，然后弹出来的时候逐个比对，空间复杂度为
- 快指针一次走两步，慢指针一次走一步，快指针走完的时候，慢指针走到中间，然后将慢指针访问的节点压栈。然后从头遍历，同时弹出栈中的元素比较，这样可以节省一般的空间复杂度。空间复杂度为
不使用额外空间：快指针一次走两步，慢指针一次走一步，快指针走完的时候，慢指针走到中间，然后将后面的部分逆序，然后从头和尾进行比较。最后将顺序再转回来。空间复杂度为
#include <iostream>
#include<stdlib.h>
#include<time.h>
#include<stack>
using namespace std;
struct Node
{
int value;
Node *next;
};
typedef struct Node *Linklist;
/** 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）
始终让新结点处在开头的位置**/
void CreateListHead(Linklist *L,int n)
{
//设置的时候让头指针为空，所以后面写回文的时候出错了
Linklist p;
int i;
srand(time(0)); // 初始化随机数种子
*L = (Linklist)malloc(sizeof(struct Node));
(*L)->next = nullptr; //* 先建立一个带头结点的单链表
for (i=0; i<n; i++)
{
p = (Linklist)malloc(sizeof(Node)); //* 生成新结点
//p->value = rand()%100+1; //* 随机生成100以内的数字
p->value = 10;
p->next = (*L)->next;
(*L)->next = p; //* 插入到表头
}
}
bool visit(int c)
{
cout<<c<<" ";
return true;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
bool ListTraverse(Linklist L)
{
Linklist p=L->next;
while(p)
{
visit(p->value);
p=p->next;
}
cout<<endl;
return true;
}
// need n extra space
bool isPalindromel(Linklist head)
{
stack<Linklist> s;
Linklist cur = head->next;
Linklist p = head->next;
while(cur != nullptr)
{
s.push(cur);
cur = cur->next;
}
while(p!= nullptr)
{
if(p->value != s.top()->value)
{
cout<<p->value<<"f "<<s.top()->value<<endl;
return false;
}
p = p->next;
s.pop();
}
return true;
}
//need n/2 space
bool isPalindrome2(Linklist head)
{
if(head->next == nullptr || head->next->next == nullptr)
return false;
Linklist fast = head->next;
Linklist slow = head->next;
stack<Linklist> s;
while(fast != nullptr && fast->next->next != nullptr)
{
s.push(slow);
fast = fast->next->next;
slow = slow->next;
}
fast = head->next;
while(!s.empty())
{
if(fast->value != s.top()->value)
{
return false;
}
fast = fast->next;
s.pop();
}
return true;
}
//need O(1) space
bool isPalindrome3(Linklist head)
{
if(head->next == nullptr || head->next->next == nullptr)
return false;
Linklist fast = head->next;
Linklist slow = head->next;
while(fast != nullptr && fast->next->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;//右部分的第一个节点
slow->next = nullptr;//mid->next -> null
Linklist temp;//辅助记录数据
while(fast != nullptr)
{
temp = fast->next;
fast->next = slow;
slow = fast;
fast = temp;
}
temp = slow;
fast = head->next;
bool res = true;
while(slow!=nullptr && fast != nullptr)
{
if(slow->value != fast->value)
{
res = false;
break;
}
slow = slow->next;
fast = fast->next;
}
//恢复原来的链表
slow = temp->next;
temp->next = nullptr;
while(slow != nullptr)
{
fast = slow->next;
slow->next = temp;
temp = slow;
slow = fast;
}
return res;
}
int main()
{
Node *p;
CreateListHead(&p,20);
ListTraverse(p);
cout<<isPalindromel(p)<<endl;
cout<<isPalindrome2(p)<<endl;
cout<<isPalindrome3(p)<<endl;
return 0;
}
12.将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。
实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。 除这个要求外，对调整后的节点顺序没有更多的要求。
例如：链表9->0->4->5>1，pivot=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总 之，满 足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部 分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。
进阶： 在原问题的要求之上再增加如下两个要求。 在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左 到右的顺序与原链表中节点的先后次序一致。
例如：链表9->0->4->5->1，pivot=3。 调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到 右为0、1。在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4， 最后出现5。
如果链表长度为N，时间复杂度请达到，额外空间复杂度请达到。
解题思路
【荷兰国旗问题嘛】将节点放到数组中，使用荷兰国旗问题求解，然后再用链表连起来。需要的额外空间，且不稳定,不能保证链表中原来数据的相对位置。
【改进】：达到时间复杂度请达到，额外空间复杂度请达到，
设置三个节点类型变量，分别为less equal more ，首先遍历一遍链表，找到第一个大于等于小于pivot的节点分别赋予三个变量，然后再遍历一遍链表，将每一个部分放在相应的块中，最后将三个部分链接起来。
注意，如果某个部分没有节点也就是nullptr应该怎么处理。
#include <iostream>
#include<stdlib.h>
#include<time.h>
#include<stack>
#include<vector>
using namespace std;
struct Node
{
int value;
Node *next;
};
typedef struct Node *Linklist;
void arrPartition(vector<Linklist> &nodeArr,int pivot);
void Swap(vector<Linklist> &nodeArr,int a,int b);
/** 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）
始终让新结点处在开头的位置**/
void CreateListHead(Linklist *L,int n)
{
//设置的时候让头指针为空，所以后面写回文的时候出错了
Linklist p;
int i;
srand(time(0)); // 初始化随机数种子
*L = (Linklist)malloc(sizeof(struct Node));
(*L)->next = nullptr; //* 先建立一个带头结点的单链表
for (i=0; i<n; i++)
{
p = (Linklist)malloc(sizeof(Node)); //* 生成新结点
p->value = rand()%100+1; //* 随机生成100以内的数字
//p->value = 10;
p->next = (*L)->next;
(*L)->next = p; //* 插入到表头
}
}
bool visit(int c)
{
cout<<c<<" ";
return true;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
bool ListTraverse(Linklist L)
{
Linklist p=L->next;
while(p)
{
visit(p->value);
p=p->next;
}
cout<<endl;
return true;
}
/**荷兰国旗类似排列问题**/
//将链表转换为荷兰国旗问题，然后再将排列后的数据转换为链表
Linklist ListPartition(Linklist head,int pivot)
{
if(head->next == nullptr)
return head;
Linklist cur = head->next;
vector<Linklist> nodeArr;
int length = 0;
while(cur != nullptr)
{
nodeArr.push_back(cur);
cur = cur->next;
length++;
}
//经测试数组的值是正确的
arrPartition(nodeArr,pivot);
for(int i = 1;i<length;i++)
{
nodeArr[i-1]->next = nodeArr[i];
}
nodeArr[length-1]->next = nullptr;
Linklist res = (Linklist)malloc(sizeof(struct Node));
res->next = nodeArr[0];
return res;
}
void arrPartition(vector<Linklist> &nodeArr,int pivot)
{
int small = -1;
int big = nodeArr.size();
int index = 0;
while(index != big)
{
if(nodeArr[index]->value < pivot)
{
Swap(nodeArr,index++,++small);
}else if(nodeArr[index]->value == pivot)
{
index++;
}else
{
Swap(nodeArr,index,--big);
}
}
}
void Swap(vector<Linklist> &nodeArr,int a,int b)
{
Linklist tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
//使用几个变量来实现
Linklist ListPartition2(Linklist head,int pivot)
{
Linklist small = nullptr;
Linklist smallEnd = nullptr;
Linklist Equal = nullptr;
Linklist EqualEnd = nullptr;
Linklist big = nullptr;
Linklist bigEnd = nullptr;
Linklist cur = head->next;
while( cur != nullptr)
{
//为了便于每个部分的赋值，每个新的点接到属于的部分的时候，next为null，
//所以使用一个变量存储next的值，并将要赋值的点next设置为null，最后再变回来
head = cur->next;
cur->next = nullptr;
if(cur->value < pivot)
{
if(small ==nullptr)
{
small = cur;
smallEnd = cur;
}else
{
smallEnd->next = cur;
smallEnd = cur;
}
}
else if(cur->value == pivot)
{
if(Equal == nullptr)
{
Equal = cur;
EqualEnd = cur;
}else
{
EqualEnd->next = cur;
EqualEnd = cur;
}
}else
{
if(big == nullptr)
{
big = cur;
bigEnd = cur;
}else
{
bigEnd->next = cur;
bigEnd = cur;
}
}
cur = head;
}
cout<<"Hello World"<<endl;
//连接
if(smallEnd != nullptr)
{
smallEnd->next = Equal;
EqualEnd = (EqualEnd == nullptr)?smallEnd:EqualEnd;
}
if(EqualEnd != nullptr)
{
EqualEnd->next = big;
}
Linklist res = (Linklist)malloc(sizeof(struct Node));
res = (small != nullptr)?small:Equal != nullptr ? Equal:big;
return res;
}
int main()
{
Node *p;
CreateListHead(&p,20);
ListTraverse(p);
Linklist res = ListPartition(p,30);
ListTraverse(res);
Linklist res2 = ListPartition2(p,30);
ListTraverse(res2);
return 0;
}
13.复制含有随机指针节点的链表
【题目】 一种特殊的链表节点类描述如下：
public class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) { this.value = data; }
}
Node类中的value是节点值，next指针和正常单链表中next指针的意义 一 样，都指向下一个节点，rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。 给定一个由 Node节点类型组成的无环单链表的头节点head，请实现一个函数完成 这个链表中所有结构的复制，并返回复制的新链表的头节点。
进阶： 不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 内完成原问题要实现的函数。
解题思路：
思路1：使用哈希表实现该含有随机指针节点的链表的复制。但是使用哈希表会使用额外空间，哈希表是一种key,value结构能够实现快速查找。
思路2，使用有限变量搞定问题，使空间复杂度为O（1）：
这里涉及到C++种hash_map的使用，STL种没有hash_map，只有map,map是基于红黑树实现的，时间复杂度为，hash_map是基于哈希表实现的，时间复杂度为,C++在使用hash_map时，如果涉及自定义类型的存储，需要自己实现哈希函数和等于函数。具体参考，实现
/*
*摘要：复制含有随机指针节点的链表
*/
#include <iostream>
#include <hash_map>
using namespace std;
using namespace __gnu_cxx;
struct Node
{
int value;
Node *next;
Node *rand;
};
/**在网上看到有关STL中hash_map的文章，以及一些其他关于STL map和hash_map的资料，总结笔记如下：
1、STL的map底层是用红黑树实现的，查找时间复杂度是log(n)；
2、STL的hash_map底层是用hash表存储的，查询时间复杂度是O(1)；
3、什么时候用map，什么时候用hash_map？
这个要看具体的应用，不一定常数级别的hash_map一定比log(n)级别的map要好，hash_map的hash函数以及解决地址冲突
等都要耗时间，而且众所周知hash表是以空间换时间的，因而hash_map的内存消耗肯定要大，
一般情况下，如果记录非常大，考虑hash_map，查找效率会高很多，如果要考虑内存消耗，则要谨慎使用hash_map。**/
/**要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。**/
//使用hash_map所需要的hash函数
struct hash_Node
{
size_t operator() (const Node &node) const
{
return node.value;
}
};
//使用hash_map所需要的比较函数
struct compare_Node
{
bool operator() (const Node &n1,const Node &n2) const
{
return n1.value == n2.value && n1.next == n2.next && n1.rand == n2.rand;
}
};
//使用hash_map解决问题
Node* copyListWithRand1(Node *head)
{
hash_map<Node,Node,hash_Node,compare_Node> map;
Node *cur = head;
while(cur != nullptr)
{
Node *ptr = new Node;
ptr->value = cur->value;
ptr->next = nullptr;
ptr->rand = nullptr;
map[*cur] = *ptr; //一一对应的关系
cur = cur->next;
}
cur = head;
while(cur != nullptr)
{
map[*cur].next = cur->next;
map[*cur].rand = cur->rand;
cur = cur->next;
}
return &map[*head];
}
Node* copyListWithRand2(Node *head)
{
if(head == nullptr)
return nullptr;
Node *cur = head;
Node *next = nullptr;
//首先将不带random指针的数据拷贝到一个大链表，1->1’->2->2’->3->3’->null
while(cur != nullptr)
{
next = new Node;
next->value = cur->value;
next->next = cur->next;
next->rand = nullptr;
cur->next = next;
cur = next->next;
}
cur = head;
Node *curCopy = nullptr;
//random指针的赋值
while(cur != nullptr) //复制rand
{
next = cur->next->next;
curCopy = cur->next;
//if 1->random 存在 1’->random = 1->random->next
curCopy->rand = cur->rand != nullptr ? cur->rand->next : nullptr;
cur = next;
}
Node *res = head->next;
cur = head;
//从大的链表中分离出深度赋值的链表
//1->1’->2->2’->3->3’->null
//cur =1 next = 2 curCopy = 1' cur->next = 2 curCopy->next = 2->next = 2' cur = 2
while(cur != nullptr)
{
next = cur->next->next;//先保存cur的下一个值 next = 2
curCopy = cur->next;//cur的下一个值就是要赋值出来的值，curCopy = 1'
cur->next = next; //cur->next = 2，//一开始认为这句多余，因为与深度复制出来的链表无关，实际上是为了保持原来的链表不被破坏
//curCopy 不能只复制出这个节点，还要复制出它的下一个节点，如果next！=空，那么就是next的下一个节点，curCopy->next = 2->next = 2'
curCopy->next = next != nullptr ? next->next : nullptr;
cur = next;//cur = 2
}
return res;
}
void printListWithRand(Node *head)
{
while(head != nullptr)
{
if(head->rand != nullptr)
cout << head->value << " rand is: " << head->rand->value << endl;
else
cout << head->value << " rand is: nullptr " << endl;
if(head->next != nullptr)
cout << head->value << " next is: " << head->next->value << endl;
else
cout << head->value << " next is: nullptr " << endl;
head = head->next;
}
}
int main()
{
Node *head = nullptr;
Node *ptr = nullptr;
for(int i =0;i<4;i++)//构造链表
{
if(head == nullptr)
{
head = new Node;
head->value = i;
head->next = nullptr;
head->rand = nullptr;
ptr = head;
continue;
}
ptr->next = new Node;
ptr->rand = ptr->next;
ptr = ptr->next;
ptr->value = i;
ptr->next = nullptr;
ptr->rand = nullptr;
}
cout << "before copy:" << endl;
printListWithRand(head);
cout << "Using hash_map to copy:" << endl;
ptr = copyListWithRand1(head);
printListWithRand(ptr);
cout << "Using advanced algorithm to copy:" << endl;
ptr = copyListWithRand2(head);
printListWithRand(ptr);
return 0;
}
14.两个单链表相交的一系列问题
【题目】 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数， 如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null 即可。
要求：如果链表1的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)。
首先要确定一个问题，两个链表相交， 不是单纯地比较数值是否相等，而是比较内存地址，内存地址表示的就是两个节点是否相等，包括内存地址和值。可以分为以下几种情况：
- 两个链表都无环，可能相交，如下图图1
- 两个链表一个有环一个无环，此时两个链表不可能相交
- 两个链表都有环，这时还会细分出三种情况
–3.1两个有环链表各自成环，可以考虑两个6形状，没有相交，如下图图2
–3.2两个有环链表相交，相交点在入环之前，如下图图3
–3.3两个有环链表相交，相交点在入环之后，入下图图4
解题第一步：将问题拆解，单链表可能有环也可能无环，根据是否有环可以分析得到上面几种情况，所以首先需要判断链表是否有环，在LetCode的一个题目中有一个题目
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
链接中总结了两种实现方法，一种是借助哈希表，引入的空间复杂度，另一种是使用快慢指针访问链表，快指针比慢指针快一步，如果有环，则在环中快指针一定会追上慢指针。
在这个题目中将函数稍微修改一下，链接中实现的函数没有返回值，现在改成返回第一个入环节点。具体地，因为是单链表，所以用哈希表实现时，访问过第一个标记为true的节点就是入环节点；如果使用快慢指针实现，快慢指针相遇的时刻，快指针回到开头，改成一次走一步，快慢指针一定会在环入口处相遇。
第二步：判断两个链表是否相交，以及返回第一个相交的节点。
- 如果用哈希表实现，则首先遍历链表1，将所有节点都放到map中去，然后遍历链表2，每遍历一个节点都在map中查找，看是否有相等节点，第一个在map中找到与链表2中相同的节点就是第一个相交节点，如果遍历结束都没有相同节点，则不相交。
- 根据链表1【head1】链表2【head2】是否有环以及入环节点【loop1】【loop2】判断两个单链表的相交状况及相交的第一个节点。
如果两个链表都无环：首先分别遍历链表1和链表2 ，得到两个链表的长度length1，length2和最后一个节点end1，end2。如果，那么由于是单链表，所以两个链表不可能相交，如果说明两个链表相交，但不一定是第一个相交的节点，如果length1 =100,lenghth2=80,head1先走20步，然后一起走，一定会共同走到第一个相交的节点处。
如果两个链表都有环：如上图所示，一共有三种情况，如何区分三种情况呢？
– 如果loop1 == loop2 ，也就是入环节点相同，那么一定是图中第三种情况，这时找第一个相交节点，就变成将loop1（loop2）当成end1(end2)的两个无环链表相交的问题了。
– 如果loop1 ！= loop2，那么loop1 继续next遍历，如果直到又重新遍历到loop1节点，都没有遇到与loop2 相同的节点，则两个链表不相交，就是图中第2种情况，返回空。如果其中遇到loop2 ，那么就是图中第4种情况，两个链表在环中相交，此时返回loop1,loop2都可以。
写代码时候的一些小毛病真的很有意思。。。。。
#include <iostream>
#include <hash_map>
using namespace std;
struct Node
{
int value;
Node *next;
};
/**
利用快慢指针实现判断链表是否有环，若有环返回第一个入环节点
**/
Node* getLoopNode(Node *head)
{
if(head == nullptr || head->next == nullptr || head->next ==nullptr)
return nullptr;
Node *fast = head->next->next;
Node *slow = head->next;
while(fast != slow)
{
///我日， fast->next->next == nullptr ||fast->next == nullptr
///一开始写反了，然后一直出错。。。。。。
if(fast->next == nullptr || fast->next->next == nullptr)
{
return nullptr;
}
fast = fast->next->next;
slow = slow->next ;
}
fast = head;
while(fast != slow)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
/**两个链表都没有环**/
Node* getNoLoop(Node *head1,Node *head2)
{
if(head1 == nullptr || head2 == nullptr)
return nullptr;
Node *cur1 = head1;
Node *cur2 = head2;
int length1 = 0;
int length2 = 0;
while(cur1 != nullptr)
{
length1++;
cur1 = cur1->next;
}
while(cur2 != nullptr)
{
length2++;
cur2 = cur2->next;
}
cur1 = length1>length2 ? head1 : head2;
cur2 = cur1 ==head1 ? head2 : head1;
int tmp = (length1>=length2) ? (length1-length2) : (length2-length1);
while(tmp != 0)
{
cur1 = cur1->next;
tmp--;
}
while(cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
/**两个链表都有环**/
Node* bothLoop(Node *head1,Node *loop1,Node *head2,Node *loop2)
{
Node *cur1 = nullptr;
Node *cur2 = nullptr;
if(loop1 == loop2)
{
cur1 = head1;
cur2 = head2;
int length1 = 0;
int length2 = 0;
while(cur1 != loop1)
{
length1++;
cur1 = cur1->next;
}
while(cur2 != loop2)
{
length2++;
cur2 = cur2->next;
}
cur1 = length1>length2 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
int tmp = (length1>=length2) ? (length1-length2) : (length2-length1);
while(tmp != 0)
{
cur1 = cur1->next;
tmp--;
}
while(cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}else
{
cur1 = loop1->next;
while(cur1 != loop1)
{
if(cur1 == loop2)
return loop1;
cur1 = cur1->next;
}
return nullptr;
}
}
/**
判断两个链表是否相交，以及返回第一个相交的节点。
**/
Node* getIntersectNode(Node *head1,Node *head2)
{
if(head1 == nullptr || head2 == nullptr)
return nullptr;
Node *loop1 = getLoopNode(head1);
Node *loop2 = getLoopNode(head2);
//都没有环
if(loop1 == nullptr && loop1 == nullptr)
{
cout<<"nothing"<<endl;
return getNoLoop(head1,head2);
}
//都有环
if(loop1 != nullptr && loop2 != nullptr)
{
cout<<"both"<<endl;
return bothLoop(head1,loop1,head2,loop2);
}
//一个有环一个无环
cout<<"one"<<endl;
return nullptr;
}
void printList(Node *head)
{
while(head != nullptr)
{
if(head->next != nullptr)
cout << head->value << " next is: " << head->next->value << endl;
else
cout << head->value << " next is: nullptr " << endl;
head = head->next;
}
}
int main()
{
cout << "Hello world!" << endl;
Node *head1 = nullptr;
Node *ptr = nullptr;
for(int i = 1;i < 8 ; i++)
{
if(head1 == nullptr)
{
head1 = new Node;
head1->value = i;
head1->next = nullptr;
ptr = head1;
continue;
}
ptr->next = new Node;
ptr = ptr->next;
ptr->value = i;
ptr->next = nullptr;
}
cout<<"List 1:"<<endl;
printList(head1);
Node *head2 = new Node;
head2->value = 0;
head2->next = new Node;
head2->next->value = 9;
head2->next->next = new Node;
head2->next->next->value = 8;
head2->next->next->next = new Node;
head2->next->next->next->value = 6;
head2->next->next->next->next = new Node;
head2->next->next->next->next->value = 7;
head2->next->next->next->next->next = nullptr;
cout<<"List 2"<<endl;
printList(head2);
Node *tmp =getIntersectNode(head1,head2);
if(tmp ==nullptr)
cout<<"无相交节点"<<endl;
head1->next->next->next->next->next->next->next = head1->next->next->next; // 7->4
//cout<<"List 1:"<<endl;
//printList(head1);
head2 = new Node;
head2->value = 0;
head2->next = new Node;
head2->next->value = 9;
head2->next->next = new Node;
head2->next->next->value = 8;
head2->next->next->next = head1->next;
Node *tmp2 =getIntersectNode(head1,head2);
if(tmp2 ==nullptr)
cout<<"无相交节点"<<endl;
else
cout<<tmp2->value<<endl;
return 0;
}
上一篇： 牛人强句,找个做你的个性签名吧。
下一篇： 动物爱上冷,为笑不怕冻