链表篇（一）

水深无声 2021-12-18 22:34 247阅读 0赞

**链表篇**

#include<stdio.h>
    //测试数据
    const int arrrlens = 9;
    int arr[arrrlens] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
    
    class Node {
    public:
    	//构造函数，创建一个节点
    	Node(int el = 0, Node * ptr = NULL) {
    		infor = el;
    		next = ptr;
    	}
    	int infor;
    	Node* next;
    };
    class NodeList {
    public:
    	NodeList() {
    		head = tail = NULL;
    	}
    	~NodeList() {
    		delete head;
    		delete tail;
    	}
    	//节点插入头部
    	void printList();
    	void addToHead(int);
    	void addLoop(int);
    	Node* deleteFromHead(int);
    	int insertNode(int);
    	Node* findKthTail(Node*, int);
    	Node* findKthTail2(Node*, int);
    	int isExistLoop();
    	int LoopLength();
    	Node* getEntryNodeOfLoop();
    public:
    	Node* head, * tail;
    };
    
    void NodeList::addToHead(int node)
    {
    	Node* p = new Node(node, NULL);
    	p->next = head;
    	head = p;
    }
    //添加环
    void NodeList::addLoop(int node)
    {
    	Node* p = head, * end = NULL;
    	Node* loop_start = NULL;
    	while (p->next != NULL)
    	{
    		if (p->infor == node)
    			loop_start = p;
    		p = p->next;
    	}
    	p->next = loop_start;
    }
    //要考虑所有条件
    Node* NodeList::deleteFromHead(int node)
    {
    	Node* p = head, * q = head;
    	if (head == NULL)
    		return head;
    	if (p->infor == node)
    	{
    		q = head;
    		head = head->next;
    		delete q;
    		return head;
    	}
    	while (p->next != NULL)
    	{
    		if (p->next->infor == node)
    		{
    			q = p->next;
    			p->next = p->next->next;
    			delete q;
    			break;
    		}
    		p = p->next;
    	}
    	if (p->next == NULL)
    		printf("not find node...\n");
    	return head;
    }
    //插入节点
    int NodeList::insertNode(int node)
    {
    	Node* p = head;
    	Node* inode = new Node(node);
    	if (p->infor <= node)
    	{
    		inode->next = head->next;
    		head->next = inode;
    		return 0;
    	}
    	while (p->next != NULL)
    	{
    		if (p->next->infor <= node)
    		{
    			inode->next = p->next->next;
    			p->next = inode;
    			return 0;
    		}
    		p = p->next;
    	}
    	return 0;
    }
    //find the kth Tail 使用递归
    int num = 0;
    Node* NodeList::findKthTail(Node* phead, int k)
    {
    	num = k;
    	if (phead == NULL)
    		return NULL;
    	Node* pCur = findKthTail(phead->next, k);
    	if (pCur != NULL)
    		return pCur;
    	else {
    		num--;
    		if (num == 0)
    			return phead;
    		return NULL;
    	}
    }
    //双指针法 find the kth Tail
    Node* NodeList::findKthTail2(Node* phead, int k)
    {
    	Node* p = head, * q = head;
    	if (head == NULL || k == 0)
    		return NULL;
    	while (q != NULL && k)
    	{
    		q = q->next;
    		k--;
    	}
    	while (q != NULL)
    	{
    		p = p->next;
    		q = q->next;
    	}
    	if (k > 0)
    		return NULL;
    	return p;
    }
    //判断是否为环
    int NodeList::isExistLoop()
    {
    	Node* slow = head, * fast = head;
    	//到结尾两个指针相遇
    	while (slow != NULL && fast->next != NULL)
    	{
    		slow = slow->next;
    		fast = fast->next->next;
    		if (slow == fast)
    			return 1;
    	}
    	return 0;
    }
    //计算环的长度，找到第二次相遇点即可
    int NodeList::LoopLength()
    {
    	Node* slow = head, * fast = head;
    	int count = 1;
    	while (slow != NULL && fast->next != NULL)
    	{
    		slow = slow->next;
    		fast = fast->next->next;
    		if (slow == fast)
    			break;
    	}
    	slow = slow->next;
    	fast = fast->next->next;
    	while (slow != fast)
    	{
    		slow = slow->next;
    		fast = fast->next->next;
    		count++;
    
    	}
    	return count;
    }
    //得到环的入口节点
    Node* NodeList::getEntryNodeOfLoop()
    {
    	Node* meetingNode = NULL;
    	Node* slow = head, * fast = head;
    	//到结尾两个指针相遇
    	while (slow != NULL && fast->next != NULL)
    	{
    		slow = slow->next;
    		fast = fast->next->next;
    		if (slow == fast)
    		{
    			meetingNode = fast;
    			break;
    		}
    	}
    	Node* p1 = head, *p2 = meetingNode;
    	while (p1 != p2 )
    	{
    		p1 = p1->next;
    		p2 = p2->next;
    	}
    	printf("Entry Node of Loop: %d \n", p1->infor);
    	return p1;
    }
    
    void NodeList::printList()
    {
    	Node* p = head;
    	int count = 0;
    	while (p != NULL && count < arrrlens)
    	{
    		printf("%d ", p->infor);
    		p = p->next;
    		count++;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	NodeList nlist;
    	for (int i = 0; i < arrrlens; i++)
    		nlist.addToHead(arr[i]);
    	//设置6为环的入口节点
    	nlist.addLoop(6);
    	nlist.printList();
    	int is = nlist.isExistLoop();
    	printf("%d \n", is);
    	int len = nlist.LoopLength();
    	printf("len = %d \n", len);
    	nlist.printList();
    	nlist.getEntryNodeOfLoop();
    }