首页 > 代码库 > 快慢指针和链表原地反转
快慢指针和链表原地反转
1，制作环型链表
2。检測链表中是否存在环（參考文章）
3。计算链表中环的长度
4， 计算链表中环起始的位置
5，推断一个链表是否存在回文，要求O（n）时间和O（1）空间的复杂度（推断链表是否是回文，要求O(n)时间。O(1)空间）
6。计算链表中间位置
7，链表原地反转（链表原地反转）
8，測试code
#include <iostream>
using namespace std;
/*
@1: detect if there is a circule in a list -> detect_circule_exist
@2: calculate the circule length in the list -> give_circ_len
@3: locate the place where the circule starts -> locate_circ_place
@4: detect if the list is palindrome -> time:o(n) and space:o(1)
*/
/*
struct simple linked list
*/
struct item
{
int n;
struct item *next;
};
class iter {
struct item *head;
int circ_len;
public:
void insert(int i);
bool remove(int i);
iter(){this->circ_len = 0;this->head = new(struct item);this->head->next = NULL;}
bool create_circule(int i);
void remove_circule();
bool detect_circule_exist();
int give_circ_len();
int locate_circ_place();
bool detect_palindrome();
void display();
~iter();
};
void iter::insert(int i) {
struct item *cur;
struct item *add_item = new(struct item);
add_item->n = i;
add_item->next = NULL;
/* insert at tail */
cur = this->head;
while(cur->next) {
cur = cur->next;
}
cur->next = add_item;
cout << add_item <<endl;
}
bool iter::remove(int i)
{
struct item *cur = this->head->next, *prev = this->head;
while (cur) {
if (cur->n == i) {
prev->next = cur->next;
return true;
} else {
cur = cur->next;
prev = prev->next;
}
}
return false;
}
void iter::display()
{
struct item *cur = this->head->next;
while (cur){
cout << cur->n << " -> ";
cur = cur->next;
}
cout <<"end" << endl;
}
/* create a circult at value: i, if not i exist return false*/
bool iter::create_circule(int i)
{
struct item *cur = this->head;
struct item *find = NULL;
while (cur->next){
cur = cur->next;
if (cur->n == i) {
find = cur;
}
}
if (find) {
cur->next = find;
return true;
} else
return false;
}
/* detect if exist a circule in the linked list */
bool iter:: detect_circule_exist()
{
/*quick and slow point to the first element of the linked list*/
struct item *quick, *slow, *mark;
bool find = false;
slow = this->head->next;
quick = this->head->next->next;
while (quick && slow) {
if (!find) {
if (quick == slow) {
find = true;
mark = slow;
slow = slow->next;
this->circ_len++;
} else {
if (!quick->next || !quick->next->next)
break;
if (!slow->next)
break;
quick = quick->next->next;
slow = slow->next;
}
} else {
if (mark == slow) {
return true;
} else {
slow = slow->next;
this->circ_len++;
}
}
}
find = false;
return find;
}
int iter:: give_circ_len()
{
this->detect_circule_exist();
return this->circ_len;
}
/* cal the len of non circule at the linked list */
int iter:: locate_circ_place()
{
if (this->detect_circule_exist()) {
struct item *quick, *slow;
int i = this->circ_len;
slow = this->head->next;
quick = this->head->next;
while (quick && i--) {
quick = quick->next;
}
i = 0;
while (quick && slow) {
if (quick == slow) {
return i;
} else {
i++;
quick = quick->next;
slow = slow->next;
}
}
} else {
return 0;
}
}
void iter:: remove_circule()
{
struct item *tail = this->head;
struct item *mark;
int i = this->locate_circ_place() + 1;
while (tail->next && i--){
tail = tail->next;
}
mark = tail;
while (tail) {
if (tail->next == mark) {
tail->next = NULL;
return;
} else {
tail = tail->next;
}
}
}
bool iter:: detect_palindrome()
{
struct item *quick, *slow;
/*first find the middle place of the linked list by quick and slow pointer*/
slow = this->head->next;
quick = this->head->next->next;
while (slow) {
struct item *mark;
slow = slow->next;
quick = quick->next->next;
if (!quick) {
/*reverse the linked list at the place*/
mark = slow;
quick = slow->next->next; /*q*/
slow = slow->next; /*p*/
struct item *temp;
while (quick) {
temp = quick->next;
quick->next = slow;
slow = quick;
quick = temp;
}
mark->next->next = NULL;
mark->next = slow;
slow = this->head->next;
mark = mark->next;
while (slow && mark) {
//cout << "odd first part: "<< slow->n << "addr:" << slow << "second part: " << mark->n << "addr:" << mark <<endl;
if (slow->n != mark->n)
return false;
else {
slow = slow->next;
mark = mark->next;
}
}
return true;
}
if (!quick->next) {
/*reverse the linked list at the place*/
mark = slow;
quick = slow->next->next; /*q*/
slow = slow->next; /*p*/
struct item *temp;
while (quick) {
temp = quick->next;
quick->next = slow;
slow = quick;
quick = temp;
}
mark->next->next = NULL;
mark->next = slow;
slow = this->head->next;
mark = mark->next;
while (slow && mark) {
//cout << "even first part: "<< slow->n << "addr:" << slow << "second part: " << mark->n << "addr:" << mark <<endl;
if (slow->n != mark->n)
return false;
else {
slow = slow->next;
mark = mark->next;
}
}
return true;
}
}
}
iter::~iter()
{
struct item *cur = this->head->next;
if (this->detect_circule_exist())
this->remove_circule();
while (cur){
struct item *temp = cur;
cur = cur->next;
delete temp;
//cout <<"delete" << temp<< endl;
}
delete this->head;
}
int main()
{
class iter myiter;
/*
for (int i = 0; i < 10; i++) {
myiter.insert(i);
}
myiter.create_circule(2);
if (myiter.detect_circule_exist())
cout << "detect circule exist and circ len" << myiter.give_circ_len()<< endl;
else
cout << "no detect circule exist" <<endl;
cout << "circ point index" << myiter.locate_circ_place() <<endl;
myiter.remove_circule();
myiter.display();
*/
/*
myiter.insert(1);
myiter.insert(2);
myiter.insert(3);
myiter.insert(3);
myiter.insert(2);
myiter.insert(1);
if (myiter.detect_palindrome())
cout << "even detect palindrome" <<endl;
else
cout << "even no detect palindrome" <<endl;
*/
myiter.insert(1);
myiter.insert(2);
myiter.insert(3);
myiter.insert(2);
myiter.insert(1);
if (myiter.detect_palindrome())
cout << "odd detect palindrome" <<endl;
else
cout << "odd no detect palindrome" <<endl;
return 1;
}
快慢指针和链表原地反转
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。