路漫漫

john的博客

发表于 更新于 分类于 ，
本文字数： 1.2k 阅读时长 ≈ 1 分钟 
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
64
65
66
67
68
69
//2021/05/27H:\无额外空间的栈逆序-使用递归\无额外空间的栈逆序-使用递归.vcxproj
#include <iostream>
#include <stack>
using namespace std;

int getDownItem(stack<int>& s);
void rStack(stack<int>& s);

void printStack(stack<int> s)
{
	if (s.empty()){
		return;
	}
	cout << s.top() << endl;
	s.pop();
	printStack(s);
}

void test()
{
	stack<int> mys;
	mys.push(4);
	mys.push(3);
	mys.push(2);
	mys.push(1);
	printStack(mys);

	//cout << getDownItem(mys) << endl;
	cout << "逆序之后" << endl;
	rStack(mys);
	printStack(mys);
}

//主要功能函数，实现栈的逆序，并且不使用额外内存空间
//函数1 实现取到栈底元素，并且弹出栈底元素
int getDownItem(stack<int>& s)
{
	int result = s.top();
	s.pop();
	//base case
	if (s.empty()) {
		return result;	//只有一个元素，栈底就是栈头
	}
	int last = getDownItem(s);		//取到剩余部分栈底元素，并且弹出栈底元素
	s.push(result);
	return last;
}

//函数2  实现栈的逆序
void rStack(stack<int>& s)
{
	if (s.empty()) {
		return;
	}
	int ret = getDownItem(s);	//得到栈底元素，并且原栈中该元素已弹出
	rStack(s);					//对剩下的部分逆序
	s.push(ret);				//把元素压回去
}



int main()
{
	test();
	
	cout << "hello world!" << endl;
	system("pause");
	return 0;
}

发表于 更新于 分类于 ，
本文字数： 2.1k 阅读时长 ≈ 2 分钟

方案一

使用栈，将链表全部入栈，然后比较链表和栈顶，相同就出栈和链表向后移动
时间复杂度：O（n）
空间复杂度：O（n）

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
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        
        
        ListNode* tmp = head;
        if (!tmp || !tmp->next) return true;

        //开辟一个栈
        stack<int> stackval;
        while (tmp)
        { 
            stackval.push(tmp->val);
            tmp = tmp->next;
        }

        //比较
        while (head)
        {
            if (head->val != stackval.top()) 
            {
                return false;               
            }
            stackval.pop();  
            head = head->next;
        }

        return true;
    }
};

在这里插入图片描述

阅读全文 »