• c++数据结构算法复习基础-- 3 --线性表-单向链表-笔试面试常见问题

    1、单链表逆序

    思路图

    在这里插入图片描述

    代码实现

    //著: 链表结构里记得加 friend void ReverseLink(Clink& link);
void ReverseLink(Clink& link)
{
	Node* p = link.head_->next_;
	while( p == nullptr)
	{
		return;
	}
	Node* q = p->next_;

	link.head_->next_ = nullptr;

	while(p != nullptr)
	{
		Node* q = p->next_;

		//p指针指向的节点进行头插
		p->next_ = link.head_->next_;
		link.head_->next_ = p;

		p = q;
	}

	/*
	Node* p = link.head_->next_;
	if( p == nullptr)
	{
		return;
	}
	Node* q = p->next_;

	link.head_->next_ = nullptr;

	while( q != nullptr)
	{
		link.head_->data_ = p->data_;
		p->next_ = link.head_;
		link.head_ = p;
		p = q;
		q = p->next_;
	}
	link.head_->data_ = p->data_;
	p->next_ = link.head_;
	link.head_ = p;
	p = nullptr;
	*/
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    测试

    int main()
{
	Clink link;
	Clink link2;
	srand(time(0));
	for(int i = 0; i<10; i++)
	{
		int val = rand() % 100;
		link.InsertTail(val);
	}

	link.show();
	cout << endl;

	ReverseLink(link);
	ReverseLink(link2);

	link.show();
	cout << endl;
	link2.show();
	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    运行结果

    在这里插入图片描述

    2、单链表倒数第k个节点

    思路图

    双指针同步位移，两个指针相聚k个节点
    在这里插入图片描述

    代码实现

    //求倒数第k个节点的值
bool MyGetLastKNode(Clink& link,int k,int& val)
{
	if(k<1)
	{
		return 0;
	}

	Node* p = link.head_;
	if( p == nullptr)
	{
		return false;
	}
	Node* pre = link.head_;

	for(int i = 0; i < k ; i++)
	{
		pre = pre->next_;

		if( pre == nullptr )
		{
			return false;
		}
	}
	//p在头节点，pre在正数第k个节点
	while( pre != nullptr )
	{
		p = p->next_;
		pre = pre->next_;
	}

	val = p->data_;
	return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    代码测试

    int main()
{
	Clink link;
	Clink link2;
	srand(time(0));
	for(int i = 0; i<10; i++)
	{
		int val = rand() % 100;
		link.InsertTail(val);
	}

	link.show();
	cout << endl;

	int val=0;
	if(MyGetLastKNode(link,3,val))
	{
		cout<< "k == 3   ";
		cout<< "find  " << val<< endl;
	}
	else
	{
		cout<< "k == 3   ";
		cout<< "false" << endl;
	}
	
	if(MyGetLastKNode(link,0,val))
	{
		cout<< "k == 0   ";
		cout<< "find  " << val<< endl;
	}
	else
	{
		cout<< "k == 0   ";
		cout<< "false" << endl;
	}

	if(MyGetLastKNode(link,12,val))
	{
		cout<< "k == 12   ";
		cout<< "find  " << val<< endl;
	}
	else
	{
		cout<< "k == 12   ";
		cout<< "false" << endl;
	}

	if(MyGetLastKNode(link2,3,val))
	{
		cout<< "k2 == 3   ";
		cout<< "find  " << val<< endl;
	}
	else
	{
		cout<< "k2 == 3   ";
		cout<< "false" << endl;
	}
	

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    运行结果

    在这里插入图片描述

    3、并两个有序单链表

    思路图

    在这里插入图片描述

    代码实现

    //合并两个有序单链表
bool MergeLink(Clink& link1,Clink& link2)
{
	Node* p = link1.head_->next_;
	Node* q = link2.head_->next_;
	Node* last = link1.head_;
	link2.head_->next_ = nullptr;

	while(p != nullptr && q != nullptr)
	{
		if(p->data_ < q->data_)
		{
			last->next_ = p;
			p = p->next_;
			last = last->next_;
		}
		else
		{
			last->next_ = q;
			q = q->next_;
			last = last->next_;
		}
	}
	if(p != nullptr)
	{
		last->next_ = p;
	}
	else
	{
		last->next_ = q;
	}

		/*
	Node* pre = link1.head_;
	Node* p = link1.head_->next_;
	Node* q = link2.head_->next_;

	while(q != nullptr)
	{
		if(p == nullptr && q != nullptr)
		{
			pre->next_ = q;
			link2.head_->next_ = nullptr;
			return true;
		}
		else if(p->data_ <= q->data_)//这里假设从小到大
		{
			p = p->next_;
			pre = pre->next_;
		}
		else 
		{
			link2.head_->next_ = q->next_;
			pre->next_=q;
			q->next_ = p;
			pre=q;
			q = link2.head_->next_;
		}
	}
	*/

	return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    运行结果

    在这里插入图片描述

    4、判断单链表是否存在环以及入口节点

    思路图

    在这里插入图片描述

    代码实现

    //判断单链表是否存在环以及入口节点
//这里参数为Node,方便测试
//记得 friend
bool IsLinkHasCirle(Node* head,int& val)
{
	Node* fast = head;
	Node* slow = head;

	while(fast != nullptr && fast->next_ != nullptr)
	{
		slow = slow->next_;
		fast = fast->next_->next_;

		if(slow == fast)
		{
			//快慢指针再次相遇，链表存在环
			fast = head;
			while(fast != slow)
			{
				slow = slow->next_;
				fast = fast->next_;
			}
			val = slow->data_;
			return true;
		}
	}
	return false;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    测试

    int main()
{
	Node head;

	Node n1(25),n2(61),n3(312),n4(118);

	head.next_ = &n1;
	n1.next_ = &n2;
	n2.next_ = &n3;
	n3.next_ = &n4;

	n4.next_ = &n2;

	int val;
	if(IsLinkHasCirle(&head,val))
	{
		cout<< "链表存在环，环的入口节点是： "<< val << endl;
	}

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    运行结果

    在这里插入图片描述

    5、判断两个链表是否相交

    在这里插入图片描述

    思路图

    在这里插入图片描述

    代码实现

    //判断两个链表是否相交,如果相交，返回相交节点的值
bool IsLinkHasMerge(Node* head1,Node* head2,int &val)
{
	int cnt1 = 0,cnt2 = 0;

	Node* p = head1->next_;
	Node* q = head2->next_;

	//计算两个链表的长度
	while(p != nullptr)
	{
		p = p->next_;
		cnt1++;
	}
	while(q != nullptr)
	{
		q = q->next_;
		cnt2++;
	}

	p = head1->next_;
	q = head2->next_;

	if(cnt1 > cnt2)
	{
		//第一个链表长
		cnt1 = cnt1-cnt2;
		while(cnt1 >0)
		{
			p = p->next_;
			cnt1--;
		}
	}
	else
	{
		//第二个链表长
		cnt2 = cnt2 -cnt1;
		while(cnt2 > 0)
		{
			q = q->next_;
			cnt2--;
		}
	}

	while(p != nullptr && q != nullptr)
	{
		if(p == q)
		{
			val = p->data_;
			return true;
		}
		p = p->next_;
		q = q->next_;
	}
	return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56

    测试代码

    int main()
{
	Node head1;
	Node head2;


	Node n1(25),n2(61),n3(312),n4(118),n5(18);
	Node nn1(1),nn2(2);

	head1.next_ = &n1;
	n1.next_ = &n2;
	n2.next_ = &n3;
	n3.next_ = &n4;
	n4.next_ = &n5;

	head2.next_ = &nn1;
	nn1.next_ = &nn2;
	nn2.next_ = &n3;

	int val;
	if(IsLinkHasMerge(&head1,&head2,val))
	{
		cout<< "两个链表相交，相交的节点是： "<< val << endl;
	}

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    运行结果

    在这里插入图片描述

    6、删除链表倒数第N个节点

    思维图

    在这里插入图片描述

    代码实现

    //这里使用利扣刷题
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //在函数内部给链表增加一个头节点，以解决不带头节点的单链表
        //head_->next   head
        ListNode* head_ = new ListNode(0,head);

        ListNode* first = head;
        ListNode* second = head_;

        for(int i = 0; i < n; i++)
        {
             first = first->next;
        }
        while(first)
        {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = head_->next;
        delete head_;
        return ans;;
    }
    
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    7、旋转链表

    思路图

    在这里插入图片描述

    代码实现

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode*p = head;
        ListNode*q = head;

        if(head == nullptr || k == 0)
        {
            return head;
        }

        int number = 0;//判断链表的长度
        for(ListNode *k = head; k != nullptr; k = k->next)
        {
            number++;
        }

        k = k%number;

        for(int i = 0; i < k; i++)
        {
            p = p->next;
        }

        while(p->next != nullptr)
        {
            q = q->next;
            p = p->next;
        }

        p->next = head;
        head = q->next;
        q->next = nullptr;

        return head;


    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
  • 相关阅读:
    Redis Key-Value数据库 【高级】
    泰迪智能科技助力中山三院放射科搭建生成式大模型应用
    【2023.11.6】OpenAI发布会——近期chatgpt被攻击，不能使用
    R语言实现竞争风险模型（1）
    SpringCloudGateway网关实战（二）
    css 设置网页最小字体为12px
    CentOS7搭建keepalived+DRBD+NFS高可用共享存储
    Oracle的优化控制器optimizer_mode参数说明以及设置
    Kotlin高仿微信-第3篇-主页
    CSRF漏洞利用与防御
  • 原文地址：https://blog.csdn.net/kyrie_sakura/article/details/136344682