当前位置：首页 > article >正文

[leetcode]链表基础回顾

article 2025/1/16 16:17:55

一.创建带头节点的链表

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef struct Node {
char ch;
Node* next;
}*LinkList,ListNode;

void printLinkList(LinkList& head)
{
   LinkList p = head->next;
   while (p != NULL)
   {
       cout << p->ch << " ";
       p = p->next;
   }
}

int main() {
   Node* head = new Node;
   head->next = nullptr;
   Node* p = head;
   Node* s = nullptr;
   char ch;

   cout << "Enter characters to build the list (use '#' to stop): ";
   while (cin >> ch && ch != '#') {
       s = new Node(); // 创建新节点，初始化 ch 和 next 为 nullptr
       s->ch = ch;
       s->next = nullptr;
       p->next = s;
       p = s;
   }

printLinkList(head);

return 0;
}

二.遍历单链表

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef struct Node {
char ch;
Node* next;
}*LinkList,ListNode;

void printLinkList(LinkList& head)
{
   LinkList p = head->next;
   while (p != NULL)
   {
       cout << p->ch << " ";
       p = p->next;
   }
}

int main() {
   Node* head = new Node;
   head->next = nullptr;
   Node* p = head;
   Node* s = nullptr;
   char ch;

printLinkList(head);

return 0;
}

三.添加新节点

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef struct Node {
char ch;
Node* next;
}*LinkList,ListNode;

void printLinkList(LinkList& head)
{
   LinkList p = head->next;
   while (p != NULL)
   {
       cout << p->ch << " ";
       p = p->next;
   }
}

void push_back(LinkList& head, char ch)
{
   LinkList newNode = new Node;
   newNode->next = NULL;
   newNode->ch = ch;
   LinkList p = head;
   while (p->next != nullptr)
   {
       p = p->next;
   }
   p->next = newNode;

}

int main() {
   Node* head = new Node;
   head->next = nullptr;
   Node* p = head;
   Node* s = nullptr;
   char ch;

return 0;
}

四.计算链表长度

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef struct Node {
char ch;
Node* next;
}*LinkList,ListNode;

void printLinkList(LinkList& head)
{
   LinkList p = head->next;
   while (p != NULL)
   {
       cout << p->ch << " ";
       p = p->next;
   }
}

}

int size(LinkList head)
{
   int len = 0;
   int size = 0;
   ListNode* p = head->next;
   while (p != NULL)
   {
       size++;
       p = p->next;
   }
   return len;
}

int main() {
   Node* head = new Node;
   head->next = nullptr;
   Node* p = head;
   Node* s = nullptr;
   char ch;

return 0;
}

五.插入新节点

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef struct Node {
char ch;
Node* next;
}*LinkList,ListNode;

void printLinkList(LinkList& head)
{
   LinkList p = head->next;
   while (p != NULL)
   {
       cout << p->ch << " ";
       p = p->next;
   }
}

}

int size(LinkList head)
{
   int len = 0;
   int size = 0;
   ListNode* p = head->next;
   while (p != NULL)
   {
       size++;
       p = p->next;
   }
   return len;
}

void insert(LinkList& head, int index,char ch)//index从head开始算为0到size
{
int len = size(head);
LinkList p = head->next;

   for (int i = 1; i < index - 1; i++)
   {
       p = p->next;
   }
   LinkList newNode = new Node;
   newNode->ch = ch;
   newNode->next = p->next;
   p->next = newNode;
}

int main() {
   Node* head = new Node;
   head->next = nullptr;
   Node* p = head;
   Node* s = nullptr;
   char ch;

六.删除节点

void deleteList(LinkList& head, int index) {
    if (head == nullptr || head->next == nullptr || index < 0) {
        // 如果链表为空或索引无效，不执行任何操作
        return;
    }

    LinkList p = head; // p 用于遍历链表，从头节点开始
    if (index == 0) {
        // 如果要删除的是头节点的下一个节点
        LinkList temp = head->next; // 保存要删除的节点
        head->next = temp->next;    // 更新头节点的 next 指针，跳过要删除的节点
        delete temp;               // 释放要删除节点的内存
        return;
    }

    // 找到要删除节点的前一个节点
    for (int i = 1; i < index; i++) {
        if (p->next == nullptr) {
            // 如果索引超出链表范围，不执行任何操作
            return;
        }
        p = p->next;
    }

    if (p->next == nullptr) {
        // 如果索引超出链表范围，不执行任何操作
        return;
    }

    LinkList temp = p->next; // 保存要删除的节点
    p->next = temp->next;  // 更新前一个节点的 next 指针，跳过要删除的节点
    delete temp;           // 释放要删除节点的内存
}

查看全文

http://www.kler.cn/a/505218.html