嘤嘤嘤当初数据结构没学好，只能现在来补啦

链表(linked-list)：链表就是线性表的链式存储方式。链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的元素串起来。

单向链表

单向链表就如图所示

1
2
3
4
head为头指针
head->val=data1;
head->next=data2的指针域
head->next->val=data2

操作

创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct node
{
    int val;
    struct node* next;
}Node;

Node* CreateNode(int val)
{
    Node* newnode=(Node*)malloc(sizeof(Node));  //创建一个链表
    if(newnode==NULL)   //判断链表是否是空链表
    {
        cout<<"out of memory"<<endl;
        return NULL;
    }
    else              //对链表进行初始化
    {
        newnode->val=val;
        newnode->next=NULL;
        return newnode;
    }
}

插入

插入有两种插入方法，一种是头插法，一个是尾插法

头插法

让头指针指向新结点，始终让新结点处于第一位

1
2
3
4
5
6
void Insert(Node* head,int val)
{
    Node* p=CreateNode(val);
    p->next = head->next;
    head->next=p;  //头指针指向新结点
}
尾插法

新的结点插在尾结点的后面（所以需要定义一个尾结点）

1
2
3
4
5
6
void Insert(Node* tail,int val)
{
    Node* p=CreateNode(val);
    tail->next=p;    //尾指针指向新结点
    tail=p->next;    //更新尾指针
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Delete(Node *head,int val)
{
    if(head->next==NULL)    //判断是否为空链表
    {
        cout<<"empty list"<<endl;
        return;
    }
    Node* cur=head->next,*pre=head;//定义当前指针和前一个指针
    while(cur)
    {
        if(cur->val==val)    //找到要删除的结点
            break;
        else
        {
            cur->next;
            pre->next;
        }
        
        pre->next=cur->next;  //前一个指针覆盖当前指针
        free(cur);  //释放当前指针
    }
}

反转

  • 非递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node* Reverse(Node* head)
{
    if(head==NULL)
        return head;
    else{
        Node* cur=head,*pre=NULL,*next=NULL,*pR=NULL;
        //pR为新链表的头指针
        while(cur!=NULL)
        {
            next=cur->next;
            if(next==NULL)//当next为空时，说明当前结点为尾结点
                pR=cur;
            cur->next=pre;//指针反转
            pre=cur;
            cur=next;
        }    
        return pR;
}
}
  • 递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node* Reverse(Node* head)
{
    if(head==NULL||head->next==NULL)
        return head;
    else 
    {
        Node* pR=Reverse(head->next);
        //先反转后面的链表，走到链表的末端结点
        head->next->next=head;
        //将当前结点设置为后面结点的后续结点
        head->next=NULL;
    }
    return pR;
}
例子

题目描述：

解题思路：主要的思想就是将链表分为三段（om,mn,n结尾），将mn段反转，再将这三段连起来。但我遇到的问题是，这三段我连不起来，之后我发现需要再建一个链表。然后我就发现我反转有问题，后来参考其他人的，才发现我对链表指针相互的赋值有问题，我会直接用val来代替这个节点，但实际上每个节点指针存放了val和下一个节点的地址。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==n)
            return head;
        else{
            ListNode res(0);//新建链表
            res.next=head;
            ListNode* pre=&res;//备份链表
            for(int i=1;i<m;i++)
                pre=pre->next;
            ListNode *cur=pre->next,*next=NULL;
            for(int i=m;i<n;i++)
            {
                next = cur->next;
                cur->next = next->next;
                next->next = pre->next;
                pre->next = next;
            }
            return res.next;
        }
    }
};

双向链表

与单向链表不同，双向链表不仅储存指向下一个节点的指针，也指向上一个节点的指针。双向链表可以快速找到前驱结点，但会增加大量的指针存储空间

操作

创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct node
{
    int val;
    struct node* pre;
    struct node* next;
}Node;

Node* CtreateNode(int val)
{
    Node* newnode=(Node*)malloc(sizeof(Node));
    if(newnode==NULL)
    {
        cout<<"out of memory"<<endl;
        return NULL;
    }
    else
    {
        newnode->val=val;
        newnode->pre=NULL;
        newnode->next=NULL;
        return newnode;
    }
}

插入

插入的方法和单向链表的插入类似

1
2
3
4
5
6
7
void Insert(Node* head,int val)
{
    Node* newnode=CreateNode(val);
    newnode->next=head->next;
    head->next>pre=newnode;
    head->next=newnode;
}

删除

由于双向链表中每个节点记录了它的前驱结点，所以不需要像单向链表中一样索引目的节点的前驱节点，而是可以通过目标节点直接获得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Node* Find(int val)
{
    for(Node* tmp=head;tmp!=NULL;tmp=tmp->next)
    {
        if(tmp->val==val)
            return tmp;
    }
    return NULL;
}
void Detele(Node* head,int val)
{
    Node* p=Find(val);
    if(p==NULL)
    {
        cout<<"Can't Find"<<endl;
        return;
    }
    p->pre->next=p->next;
    p->next->pre=p->pre;
    free(p);
}