判断单链表是否有环、有序单链表去重、单链表逆置、爬楼梯问题、字符串转整形

判断单链表是否有环：

//#include <iostream>
//using namespace std;
//
//struct Node {
//    int data;
//    Node* next;
//};
//
判断单链表是否存在环，参数circleNode是环内节点
//bool hasCircle(Node* head, Node*& circleNode)
//{
//    Node* slow, * fast;
//    slow = fast = head;
//    while (fast != NULL && fast->next != NULL)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            circleNode = fast;
//            return true;
//        }
//    }
//    return false;
//}
//
找到环的入口点
//Node* findLoopPort(Node* head)
//{
//    //如果head为空，或者为单节点，则不存在环
//    if (head == NULL || head->next == NULL) return NULL;
//
//    Node* slow, * fast;
//    slow = fast = head;
//
//    //先判断是否存在环
//    while (fast != NULL && fast->next != NULL)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            break;
//        }
//    }
//
//    if (fast != slow) return NULL;  //不存在环
//
//    fast = head;                    //快指针从头开始走，步长变成1
//    while (fast != slow)            //两者相遇即为入口点
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    return fast;
//}
//
//int main()
//{
//    Node head;
//    head.data = 0;
//
//    Node n1;
//    n1.data = 1;
//    head.next = &n1;
//
//    Node n2;
//    n2.data = 2;
//    n1.next = &n2;
//
//    Node n3;
//    n3.data = 3;
//    n2.next = &n3;
//
//    Node n4;
//    n4.data = 4;
//    n3.next = &n4;
//
//    Node n5;
//    n5.data = 5;
//    n4.next = &n5;
//
//    Node n6;
//    n6.data = 6;
//    n5.next = &n6;
//    n6.next = &n3;  //节点6指向节点3，形成一个环，入口为节点3
//
//    Node* meetNode;
//    bool ret = hasCircle(&head, meetNode);
//    cout << "has circle:" << ret << "meet node:" << meetNode->data << endl;
//
//    Node* entrance;
//    entrance = findLoopPort(&head);
//    cout << "entrance:" << entrance->data << endl;
//
//    return 0;
//}


#include<iostream>
#include<assert.h>
using namespace std;


struct node
{
	node* next;
	int data;
};


bool hasCircle(node* head)
{
	assert(head);
	node* fast = head;
	node* slow = head;
	while (fast != NULL && fast->next != NULL)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
		{
			return true;
		}
	}
	return false;
}

int main()
{
	node head;
	head.data = 0;

	node data1;
	data1.data = 1;
	head.next = &data1;


	node data2;
	data2.data = 2;
	data1.next = &data2;

	node data3;
	data3.data = 3;
	data2.next =&data3;


	//data3.next = NULL;

	data3.next = &data1;

	if (hasCircle(&head))
	{
		cout << "有环" << endl;
	}
	else
	{
		cout << "无环" << endl;
	}
	
	return 0;

}

有序单链表去重：

//0 1 1 1 2 2 ->0 1 2
#include<iostream>
using namespace std;

struct ListNode {
    int data;
    ListNode* next;
};



ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return head;
    ListNode* p = head;
    ListNode* q = p->next;
    while (q)
    {
        if (q->data == p->data) {  // 如果指针q指向的元素值与指针p指向的元素值相等，那么q向后移动一位
            q = q->next;
        }
        else {
            if (!p->next) delete p->next;  // 避免野指针 
            p->next = q;  // 指针p的next指向指针q的位置
            p = q;  // 指针p向后移动至指针q的位置
            q = q->next;  // 指针q向后移动一个位置
        }
    }
    if (!p->next) delete p->next;  // 避免野指针

    p->next = q;   // 千万不要忘记！循环结束后把p的next置为q
    return head;
}

int main()
{
    ListNode head;
	head.data = 0;

    ListNode data1;
	data1.data = 1;
	head.next = &data1;


    ListNode data2;
	data2.data = 1;
	data1.next = &data2;

    ListNode data3;
	data3.data = 1;
	data2.next = &data3;


    ListNode data4;
	data4.data = 2;
	data3.next = &data4;

    ListNode data5;
	data5.data = 2;
	data4.next = &data5;

    data5.next = NULL;

    cout << "删除前" << endl;
    ListNode* temp = &head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;



    ListNode* res= deleteDuplicates(&head);
    cout << "删除后：" << endl;
    while (res != NULL)
    {
        cout << res->data<<" ";
        res = res->next;
    }


    return 0;

}

单链表逆置：

#include<iostream>
using namespace std;

struct ListNode {
	int data;
	ListNode* next;
};

//单链表逆置  1 2 3 4 5   -> 5 4 3 2 1
ListNode* reverseList(ListNode* plist)
{
	ListNode* cur = plist;
	ListNode* prev = NULL;
	ListNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}

int main()
{
	ListNode head;
	head.data = 0;

	ListNode data1;
	data1.data = 1;
	head.next = &data1;


	ListNode data2;
	data2.data = 2;
	data1.next = &data2;

	ListNode data3;
	data3.data = 3;
	data2.next = &data3;


	ListNode data4;
	data4.data = 4;
	data3.next = &data4;

	ListNode data5;
	data5.data = 5;
	data4.next = &data5;

	data5.next = NULL;

	cout << "逆置前" << endl;
	ListNode* temp = &head;
	while (temp != NULL)
	{
		cout << temp->data << " ";
		temp = temp->next;
	}
	cout << endl;

	ListNode* res = reverseList(&head);
	cout << "逆置后：" << endl;
	while (res != NULL)
	{
		cout << res->data << " ";
		res = res->next;
	}

	return 0;

}

爬楼梯问题：

//1 2 3 5 8 13 21 

#include<iostream>
using namespace std;

int fun(int n)
{
	int f1 = 1, f2 = 2;
	int f3;
	for (int i = 1; i <= n - 2; i++)
	{
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
	}
	return f3;
}

int main()
{
	int n;
	cin >> n;
	cout << fun(n) << endl;
	return 0;
}

字符串转整形

#include<iostream>
#include<assert.h>
using namespace std;

int my_atoi(const char* s)
{
	int sign = 1;
	int res = 0;
	assert(s);
	if (*s == (const char)("\0"))
	{
		return 0;
	}
	int len = strlen(s);
	for (int i = 1; i < len; i++)
	{
		if (s[i] < '0' || s[i] > '9')
		{
			return 0;
		}
	}
	for (int i = 0; i < len; i++)
	{
		if (s[0] == '-')
		{
			sign = -1;
		}
		if (s[0] == '+')
		{
			sign = 1;
		}
		if (s[i] >= '0' && s[i] <= '9')
		{
			res = res * 10 + (s[i] - '0');
		}
	}
	return sign * res;

}

int main()
{
	const char* p = "-1234";
	int res = my_atoi(p);
	cout << res << endl;
	return 0;
}