链表问题集锦

1.单链表的初始化，输出以及插入删除的基本操作

#include <iostream>
#include <string>
using namespace std;
    
struct Node{
   int data;
   Node *next;
};

Node* IniList()
{
    Node *p,*head=NULL;
    for(int i=10;i>0;--i)
    {
        p=(Node*)malloc(sizeof(Node));
        p->data=i;
        p->next=head;
        head=p;
    }
    return head;
}
void PrintList(Node *head)
{
    Node *s=head;
    while(s->next!=NULL)
    {
        cout<<s->data<<" ";
        s=s->next;
    }
    cout<<s->data;
    cout<<endl;
}

bool InsertList(Node *head,int n,int data)
{
    Node *p=head;
    if(!p) return false;
    int i=1;
    while(p->next!=NULL && i<n)
    {
        p=p->next;
        ++i;
    }
    if(!(p->next)) return false;

    Node *s;
    s=(Node*)malloc(sizeof(Node));
    s->data=data;
    s->next=p->next;
    p->next=s;
    return true;
}

void DeletList(Node* head,int n)
{
    Node* p=head,*q;
    int i=1;
    while(p && p->next && i<n-1)
    {
        p=p->next;
        ++i;
    }
    q=p->next;
    p->next=q->next;
    free(q);
}

int main()
{
    Node *head;
    head=IniList();
    PrintList(head);
    if(InsertList(head,5,13))
        PrintList(head);
    DeletList(head,4);
    PrintList(head);
    return 0;
}

2.在O(1)时间删除链表节点

bool DeleteElem(Node *cur)
{
    if(!cur || !cur->next) return false;
    Node *p;
    p=cur->next;
    cur->data=p->data;
    cur->next=p->next;
    free(p);
    return true;
}

int main()
{
    Node *head;
    head=IniList();
    PrintList(head);
    Node *cur=head;
    int m=3;
    while(m--)
    {
        cur = cur->next;
    }
    if(DeleteElem(cur))
        PrintList(head);
    return 0;
}

3.反转单链表

Node* ReverseList(Node* head)
{
    Node *pre=NULL,*next=NULL;
    if(!head || !head->next) return head;
    while(head!=NULL)
    {
        next=head->next;
        head->next=pre;
        pre=head;
        head=next;
    }
    return pre;
}


int main()
{
    Node *head;
    head=IniList();
    PrintList(head);
    
    head=ReverseList(head);
    PrintList(head);
    return 0;
}

4.求链表倒数第k个节点

Node* theKthNode(Node* head,int k)
{
    Node *slow=head,*fast=head;
    int i;
    for(i=k;i>0 && fast->next!=NULL;--i)
        fast=fast->next;
    if(i>0) return NULL;
    
    while(fast!=NULL)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

5.求链表中间节点

Node* theMiddleNode(Node* head)
{
    Node* slow=head,*fast=head;
    if(head==NULL) return NULL;
    if(head->next==NULL) return head;

    while(fast!=NULL && fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}