关于链表的总结(C++循环实现)

时间:2023-03-09 21:32:18
关于链表的总结(C++循环实现)

0.目录

1.链表的基本操作

2.结点的基本操作

3.面试题

1.链表的基本操作

1.1 结点定义

#include <iostream>

using namespace std;

struct Node
{
int value;
Node* next;
};

1.2 创建链表

Node* createLinkedList(int data[], int len)
{
Node* ret = NULL;
Node* slider = NULL; for(int i=0; i<len; i++)
{
Node* n = new Node(); n->value = data[i];
n->next = NULL; if( slider == NULL )
{
slider = n;
ret = n;
}
else
{
slider->next = n;
slider = n;
}
} return ret;
}

1.3 销毁链表

void destroyLinkedList(Node* list)
{
while( list )
{
Node* del = list; list = list->next; delete del;
}
}

1.4 打印链表

void printLinkedList(Node* list)
{
while( list )
{
cout << list->value << "->"; list = list->next;
} cout << "NULL" << endl;
}

1.5 获取链表长度

int getListLength(Node* list)
{
int ret = 0; while( list )
{
ret++;
list = list->next;
} return ret;
}

测试:

int main()
{
int a[] = {1, 5, 3, 2, 4}; Node* list1 = createLinkedList(a, 5);
printLinkedList(list1);
cout << getListLength(list1) << endl;
destroyLinkedList(list1);
cout << endl; Node* list2 = createLinkedList(NULL, 0);
printLinkedList(list2);
cout << getListLength(list2) << endl;
destroyLinkedList(list2);
cout << endl; int b[] = {6};
Node* list3 = createLinkedList(b, 1);
printLinkedList(list3);
cout << getListLength(list3) << endl;
destroyLinkedList(list3); return 0;
}

运行结果为:

1->5->3->2->4->NULL
5 NULL
0 6->NULL
1

2.结点的基本操作

2.1 删除结点

Node* deleteNode(Node* list, int value)
{
Node* head = list;
Node* slider = NULL; while( head && (head->value == value) )
{
slider = head;
head = head->next;
slider = NULL;
} Node* ret = head; while( ret )
{
slider = ret->next; if( slider && (slider->value == value) )
{
ret->next = slider->next;
slider = NULL;
}
else
{
ret = ret->next;
}
} return head;
}

测试:

int main()
{
int a[] = {1, 2, 3, 2, 5}; Node* list1 = createLinkedList(a, 5);
printLinkedList(list1);
printLinkedList(deleteNode(list1, 2));
destroyLinkedList(list1);
cout << endl; Node* list2 = createLinkedList(NULL, 0);
printLinkedList(list2);
printLinkedList(deleteNode(list2, 2));
destroyLinkedList(list2);
cout << endl; int b[] = {2, 2, 2, 2, 2};
Node* list3 = createLinkedList(b, 5);
printLinkedList(list3);
printLinkedList(deleteNode(list3, 2));
destroyLinkedList(list3);
cout << endl; int c[] = {1};
Node* list4 = createLinkedList(c, 1);
printLinkedList(list4);
printLinkedList(deleteNode(list4, 2));
destroyLinkedList(list4); return 0;
}

运行结果为:

1->2->3->2->5->NULL
1->3->5->NULL NULL
NULL 2->2->2->2->2->NULL
NULL 1->NULL
1->NULL

2.2 查找结点

Node* findNode(Node* list, int value)
{
Node* ret = NULL;
Node* slider = list; while( slider )
{
if( slider->value == value )
{
ret = slider;
break;
}
else
{
slider = slider->next;
}
} return ret;
}

3.面试题

3.1 反转链表

Node* reverseLinkedList(Node* list)
{
Node* ret = NULL;
Node* slider = list;
Node* next = NULL; while( slider )
{
next = slider->next;
slider->next = ret;
ret = slider;
slider = next;
} return ret;
}

测试:

int main()
{
int a[] = {1, 5, 3, 2, 4}; Node* list1 = createLinkedList(a, 5);
printLinkedList(list1);
printLinkedList(reverseLinkedList(list1));
destroyLinkedList(list1);
cout << endl; Node* list2 = createLinkedList(NULL, 0);
printLinkedList(list2);
printLinkedList(reverseLinkedList(list2));
destroyLinkedList(list2);
cout << endl; int b[] = {6};
Node* list3 = createLinkedList(b, 1);
printLinkedList(list3);
printLinkedList(reverseLinkedList(list3));
destroyLinkedList(list3); return 0;
}

运行结果为:

1->5->3->2->4->NULL
4->2->3->5->1->NULL NULL
NULL 6->NULL
6->NULL

3.2 合并两个单向排序链表

Node* mergeLinkedList(Node* list1, Node* list2)
{
Node* ret = NULL; if( list1 == NULL )
{
ret = list2;
}
else if( list2 == NULL )
{
ret = list1;
}
else
{
if( list1->value < list2->value )
{
ret = list1;
list1 = list1->next;
}
else
{
ret = list2;
list2 = list2->next;
} Node* slider = ret; while( list1 && list2 )
{
if( list1->value < list2->value )
{
slider->next = list1;
list1 = list1->next;
}
else
{
slider->next = list2;
list2 = list2->next;
} slider = slider->next;
} if( list1 == NULL )
{
slider->next = list2;
}
else if( list2 == NULL )
{
slider->next = list1;
}
} return ret;
}

测试:

int main()
{
int a[] = {1, 2, 4, 6, 8}; Node* list1 = createLinkedList(a, 5);
printLinkedList(list1); int b[] = {2, 2, 3, 3, 7};
Node* list2 = createLinkedList(b, 5);
printLinkedList(list2); Node* list3 = mergeLinkedList(list1, list2);
printLinkedList(list3);
destroyLinkedList(list3); return 0;
}

运行结果为:

1->2->4->6->8->NULL
2->2->3->3->7->NULL
1->2->2->2->3->3->4->6->7->8->NULL

3.3 查找两个链表的第一个公共结点

Node* findFirstCommonNode(Node* list1, Node* list2)
{
int len1 = getListLength(list1);
int len2 = getListLength(list2);
Node* ret = NULL; if( len1 > len2 )
{
for(int i=0; i<(len1-len2); i++)
{
list1 = list1->next;
}
}
else
{
for(int i=0; i<(len2-len1); i++)
{
list2 = list2->next;
}
} while( list1 )
{
if( list1 == list2 )
{
ret = list1;
break;
}
else
{
list1 = list1->next;
list2 = list2->next;
}
} return ret;
}

测试:

int main()
{
int a[] = {1, 2, 3};
Node* list1 = createLinkedList(a, 3); int b[] = {4, 5};
Node* list2 = createLinkedList(b, 2); int c[] = {6, 7};
Node* list3 = createLinkedList(c, 2); Node* ret = NULL; ret = list1;
while( ret->next )
{
ret = ret->next;
}
ret->next = list3; ret = list2;
while( ret->next )
{
ret = ret->next;
}
ret->next = list3; printLinkedList(list1);
printLinkedList(list2); ret = findFirstCommonNode(list1, list2);
printLinkedList(ret); return 0;
}

运行结果为:

1->2->3->6->7->NULL
4->5->6->7->NULL
6->7->NULL

3.4 删除排序链表中重复的结点

Node* deleteDuplicationNode(Node* list)
{
Node* head = list;
Node* toDel = NULL;
Node* end = NULL; // 处理头结点重复的情况
while( head && head->next && (head->value == head->next->value) )
{
end = head;
// 找到最后一个与头结点重复的结点
while( end && end->next && (end->value == end->next->value) )
{
end = end->next;
}
// 删除中间与头结点重复的结点
while( head != end )
{
toDel = head;
head = head->next;
toDel = NULL;
}
// 删除最后一个与头结点重复的结点
toDel = head;
head = head->next;
toDel = NULL;
} Node* ret = head;
Node* slider = NULL; while( ret && ret->next )
{
slider = ret->next; // 处理中间结点重复的情况
while( slider && slider->next && (slider->value == slider->next->value) )
{
end = slider;
// 找到最后一个与中间结点重复的结点
while( end && end->next && (end->value == end->next->value) )
{
end = end->next;
}
// 删除中间与中间结点重复的结点
while( slider != end )
{
toDel = slider;
slider = slider->next;
toDel = NULL;
}
// 删除最后一个与中间结点重复的结点
toDel = slider;
slider = slider->next;
ret->next = slider;
toDel = NULL;
} if( ret->next == slider )
{
ret = ret->next;
}
else
{
ret->next = slider;
}
} return head;
}

测试:

int main()
{
int a[] = {1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5}; Node* list1 = createLinkedList(a, 12);
printLinkedList(list1);
printLinkedList(deleteDuplicationNode(list1));
destroyLinkedList(list1);
cout << endl; Node* list2 = createLinkedList(NULL, 0);
printLinkedList(list2);
printLinkedList(deleteDuplicationNode(list2));
destroyLinkedList(list2);
cout << endl; int b[] = {2, 3, 3, 3, 4, 4, 5, 6, 6, 7};
Node* list3 = createLinkedList(b, 10);
printLinkedList(list3);
printLinkedList(deleteDuplicationNode(list3));
destroyLinkedList(list3);
cout << endl; int c[] = {1};
Node* list4 = createLinkedList(c, 1);
printLinkedList(list4);
printLinkedList(deleteDuplicationNode(list4));
destroyLinkedList(list4); return 0;
}

运行结果为:

1->1->1->2->2->2->3->4->4->4->5->5->NULL
3->NULL NULL
NULL 2->3->3->3->4->4->5->6->6->7->NULL
2->5->7->NULL 1->NULL
1->NULL