【数据结构学习】-链表

快来打我* 2022-08-04 11:59 168阅读 0赞

链表是一种数据结构，当要保存和管理的数据元素的数目变化较大时，使用链表效率会很高。在链表中，每个元素都保存在一个称为节点的数据结构中。当新的元素加入列表时，创建新的节点来保存元素，链表中所有节点通过指针串联在一起。

对于一个链表，首先要掌握链表的基本操作，比如插入、删除、判断一个元素是否在链表中等等。以下是对链表进行基本操作的代码和解析。

#include <iostream>
    using namespace std;
    struct ListNode
    {
    	ListNode *next;
    	int val;
    	ListNode(int x): val(x),next(NULL) {}
    };
    void print(ListNode *head)		//输出链表
    {
    	ListNode *temp=head;
    	while(temp!=NULL)
    	{
    		cout<<temp->val<<"\t";
    		temp=temp->next;
    	}
    	cout<<endl;
    }
    int getsize(ListNode *head)		//得到链表的大小
    {
    	int size=0;
    	ListNode *temp=head;
    	while(temp!=NULL)
    	{
    		size++;
    		temp=temp->next;
    	}
    	return size;
    }
    void add(int index,int element,ListNode *head)		//在索引处添加节点
    {
    	ListNode *node=new ListNode(element);
    	ListNode *temp=head;
    	int size=getsize(head);
    	if(index>=size)
    	{
    		cout<<"index out of range"<<endl;
    		return;
    	}
    	if(index==0)
    	{
    		node->next=head;
    		return;
    	}
    	for(int i=1;i<index;i++)
    	{
    		temp=temp->next;
    	}
    	node->next=temp->next;
    	temp->next=node;
    }
    void remove(int index,ListNode *head)  //删除节点
    {
    	int size=getsize(head);
    	ListNode *temp=head;
    	if(index>=size)
    	{
    		cout<<"index out of range"<<endl;
    		return;
    	}
    	if(index==0)
    	{
    		head=head->next;
    		return;
    	}
    	for(int i=1;i<index;i++)
    	{
    		temp=temp->next;
    	}
    	temp->next=temp->next->next;
    }
    bool contains(ListNode *head,int element)	//判断某个值是否在链表中
    {
    	ListNode *temp=head;
    	while(temp!=NULL)
    	{
    		if(temp->val==element)
    		{
    			return true;
    		}
    		temp=temp->next;
    	}
    	return false;
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int a[5]={1,4,6,9,10};
    	ListNode *head=new ListNode(1);
    	ListNode *temp=head;
    	for(int i=1;i<5;i++)
    	{
    		temp->next=new ListNode(a[i]);
    		temp=temp->next;
    	}
    	cout<<"输出的原始链表为："<<endl;
    	print(head);
    	add(2,8,head);
    	cout<<"输出插入元素后的链表为:"<<endl;
    	print(head);
    	cout<<"链表的大小为："<<endl<<getsize(head)<<endl;
    	cout<<"链表中是否含有数值？"<<endl<<contains(head,9)<<endl;
    	cout<<"链表中是否含有数值？"<<endl<<contains(head,7)<<endl;
    	remove(4,head);
    	cout<<"输出删除元素后的链表为："<<endl;
    	print(head);
    	return 0;
    }

输出结果为：  
输出的原始链表为：  
1 4 6 9 10  
输出插入元素后的链表为:  
1 4 8 6 9 10  
链表的大小为：  
6  
链表中是否含有数值9？  
1  
链表中是否含有数值7？  
0  
输出删除元素后的链表为：  
1 4 8 6 10  
以上是链表的基本操作，链表还有一些其他比较常见的问题。比如，链表的反序、删除链表的倒数第N个节点、链表环的相关问题等。  
1.链表反序  
链表反序是比较常见的问题，很简单，直接看代码就好。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            if(head==NULL)
                return head;
            ListNode *curNode=head,*nextNode=head->next,*temp;
            while(nextNode!=NULL)
            {
                temp=nextNode->next;
                nextNode->next=curNode;
                curNode=nextNode;
                nextNode=temp;
            }
            head->next=NULL;
            head=curNode;
            return head;
        }
    };

2.删除链表倒数第N个节点  
这个有两种解法，第一种是直接把链表反序删除第N个节点即可，但是这样破坏了链表的原来的结构；第二种是声明两个指针，当第1个指针指向末尾时，让第二个节点指向倒数第N+1个节点。代码如下：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *removeNthFromEnd(ListNode *head, int n) {
            ListNode *tail,*curNode;
            tail=head;
            curNode=head;
            int length=0;
            while(curNode!=NULL)
            {
                length++;
                curNode=curNode->next;
            }
            if(length<n)
                return head;
            if(length==n)
            {
                head=head->next;
                return head;
            }
            for(int i=0;i<n+1;i++)
                tail=tail->next;
            curNode=head;
            while(tail!=NULL)
            {
                tail=tail->next;
                curNode=curNode->next;
            }
            curNode->next=curNode->next->next;
            return head;
        }
    };

3.链表环问题  
思路：声明两个指针，一个快指针，一个慢指针，如果两个指针能够相交，则说明链表中存在环。代码如下：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            ListNode *fast,*slow;
            fast=head;
            slow=head;
            while(fast!=NULL&&fast->next!=NULL)
            {
                fast=fast->next->next;
                slow=slow->next;
                if(fast==slow)
                    return true;
            }
            return false;
        }
    };

总结：链表是很重要的一部分内容，以上是常见的链表问题，其他的问题无外乎这些基本问题的变形。只要掌握了基本知识，临场多变通，就不会有问题。