力扣练习——8 链表中的下一个更大节点

8 链表中的下一个更大节点

1.问题描述
给出一个单向链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。

每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。

返回整数答案数组（代码中是vector） answer，其中 answer[i] = next_larger(node_{i+1}) 。

注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其第一个节点的值为 2，第二个节点值为 1，第三个节点值为 5 。

示例 1：

输入：[2,1,5]

输出：[5,5,0]

示例 2：

输入：[2,7,4,3,5]

输出：[7,0,5,5,0]

示例 3：

输入：[1,7,5,1,9,2,5,1]

输出：[7,9,9,9,0,5,0,0]

说明：

对于链表中的每个节点，1 <= node.val <= 10^9

给定列表的长度在 [0, 10000] 范围内

可使用以下代码，完成其中的nextLargerNodes函数，其中形参head指向无头结点单链表，返回如上描述的数组（vector）。

#include

#include

using namespace std;

struct ListNode

{

int val;

ListNode *next;

ListNode() : val(0), next(NULL) {}

ListNode(int x) : val(x), next(NULL) {}

ListNode(int x, ListNode *next) : val(x), next(next) {}
1
2
3
4
5
6
7
8
9

};

class Solution {

public:

vector<int> nextLargerNodes(ListNode* head) {

         //填充本函数完成功能  

}
1
2
3
4
5

};

ListNode *createByTail()

{

ListNode *head;

ListNode *p1,*p2;

int n=0,num;

int len;

cin>>len;

head=NULL;

while(n<len && cin>>num)

{

    p1=new ListNode(num);

    n=n+1;

    if(n==1)

        head=p1;

    else

        p2->next=p1;

    p2=p1;

}

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

}

int main()

{

ListNode* head = createByTail();

vector<int> res=Solution().nextLargerNodes(head);

for(int i=0; i<res.size(); i++)

{

    if (i>0) cout<<" ";

    cout<<res[i];

}

cout<<endl;

return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

}

2.输入说明
首先输入链表长度len，然后输入len个整数，以空格分隔。
3.输出说明
输出格式见范例
4.范例
输入
8
1 7 5 1 9 2 5 1
输出
7 9 9 9 0 5 0 0
5.代码

#include<iostream>

#include<vector>

using namespace std;



struct ListNode

{

	int val;

	ListNode *next;

	ListNode() : val(0), next(NULL) {}

	ListNode(int x) : val(x), next(NULL) {}

	ListNode(int x, ListNode *next) : val(x), next(next) {}

};

class Solution {

public:

	//思想：首先要理解清楚题意，下一个更大的结点，所以每次从当前结点往后遍历，遇到的第一个比当前结点大的结点，即为我们要找的结点；
	//若不存在这样的结点，则返回0
	vector<int> nextLargerNodes(ListNode* head) {
		
		vector<int>vec;  //这里类似于数组，只是长度可以自由调节
		
		ListNode *p = head ,*q;//p指向当前结点，q指向p的后继
	
		while (p)
		{   
			//int cur_num = p->val;
			q = p->next;
			while (q)
			{
				if (q->val > p->val)
				{
					vec.push_back(q->val); //类似于数组的赋值操作，不要和栈搞混
					break;
				}

				q = q->next;
			}
			if (q == NULL)
				vec.push_back(0);	
			p = p->next;
		}
		return vec;
	}

};

ListNode *createByTail()

{

	ListNode *head;

	ListNode *p1, *p2=NULL;

	int n = 0, num;

	int len;

	cin >> len;

	head = NULL;

	while (n<len && cin >> num)

	{

		p1 = new ListNode(num);

		n = n + 1;

		if (n == 1)

			head = p1;

		else

			p2->next = p1;

		p2 = p1;

	}

	return head;

}



int main()

{

	ListNode* head = createByTail();

	vector<int> res = Solution().nextLargerNodes(head);

	for (int i = 0; i < res.size(); i++)

	{

		if (i > 0) cout << " ";

		cout << res[i];

	}

	cout << endl;

	return 0;

}


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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126