创建一个单链表
#include <iostream>
#include<vector>
using namespace std;
struct ListNode{
int val;
struct ListNode* next;
ListNode(int x) :
val(x), next(NULL){
}
};
int main(){
int num;
cin >> num;
ListNode* head = new ListNode(num);
ListNode* p = head;
//利用尾插法创建一个链表
while (cin >> num){
ListNode* q = new ListNode(num);
p->next = q;
p = p->next;
}
//遍历这个链表,并输出每个结点的元素
ListNode* m = head;
while (m != nullptr){
cout << m->val << endl;
m = m->next;
}
return 0;
}
插入结点
ListNode* insertNode(ListNode* head, int data){
ListNode* newNode = new ListNode(data);
ListNode* p = head;
if (p == nullptr){
head = newNode;
}
else{
while (p->next != nullptr){
p = p->next;
}
p->next = newNode;
}
return head;
}
删除结点
ListNode* deleteNode(ListNode* head, int data){
ListNode* p = head;
//首先判断是不是空链表
if (p == nullptr){
return head;
}
else{
//判断是不是删除头节点
if (p->val == data){
head = p->next;
delete p;
return head;
}
else{
//如果有该结点,遍历到待删除节点的前一节点
while (p->next != nullptr && p->next->val != data){
p = p->next;
}
//遍历完整个链表都没有待删除节点
if (p->next == nullptr){
return head;
}
else{
ListNode* deleteNode = p->next;
p->next = deleteNode->next;
delete deleteNode;
return head;
}
}
}
}
反转链表
#include <iostream>
#include<vector>
using namespace std;
struct ListNode{
int val;
struct ListNode* next;
ListNode(int x) :
val(x), next(NULL){
}
};
//反转链表
ListNode* reverse(ListNode* head){
ListNode* pPrev = nullptr;
ListNode* p = head;
ListNode* pReverseHead = nullptr;
while (p != nullptr){
ListNode* pNext = p->next;
if (pNext == nullptr){
pReverseHead = p;
}
p->next = pPrev;
pPrev = p;
p = pNext;
}
return pReverseHead;
}
int main(){
int num;
cin >> num;
ListNode* head = new ListNode(num);
ListNode* p = head;
while (cin >> num){
ListNode* q = new ListNode(num);
p->next = q;
p = p->next;
}
p->next = nullptr;
ListNode* result = reverse(head);
ListNode* node = result;
while (node != nullptr){
cout << node->val << endl;
node = node->next;
}
return 0;
}
倒数第k个结点
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == nullptr || k == 0){
return nullptr;
}
ListNode* pAhead = pListHead;
//判断K是不是超出了链表的长度
for (int i = 0; i< k - 1; i++){
if (pAhead->next != nullptr){
pAhead = pAhead->next;
}
else{
return nullptr;
}
}
ListNode* pBehind = pListHead;
while (pAhead->next != nullptr){
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}
判断是否有环
//判断快慢指针是否相遇
ListNode* MeetNode(ListNode* pHead){
ListNode* pNode = pHead;
//判断链表是否为空
if(pNode == nullptr){
return nullptr;
}
//设置慢指针(慢指针不能为nullptr)
ListNode* slowNode = pNode -> next;
if(slowNode == nullptr){
return nullptr;
}
//设置快指针
ListNode* fastNode = slowNode -> next;
while(fastNode != nullptr && slowNode != nullptr){
//相遇返回快/慢指针
if(fastNode == slowNode){
return fastNode;
}
//slow走一步
slowNode = slowNode ->next;
//fast走两步(走下一步需要判读是不是为nullptr)
fastNode = fastNode -> next;
if (fastNode -> next != nullptr){
fastNode = fastNode -> next;
}
}
return nullptr;
}
//计算环中节点的个数
int Count(ListNode* pMeet){
int count = 0;
ListNode* pNode = pMeet;
while(pNode->next != pMeet){
++count;
pNode = pNode -> next;
}
++ count;
return count;
}
//计算环的入口节点
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* meetNode = MeetNode(pHead);
if (meetNode == nullptr){
return nullptr;
}
int count = Count(meetNode);
ListNode* aheadNode = pHead;
ListNode* behindNode = pHead;
for(int i = 0; i< count; i++){
aheadNode = aheadNode ->next;
}
while(aheadNode != behindNode){
aheadNode = aheadNode -> next;
behindNode = behindNode -> next;
}
ListNode* result = aheadNode;
return result;
}