Leetcode刷题——重排链表_重新排序为:l0→ln→l1→ln-1→l2→ln-2→…

重排链表

1.问题描述
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

可使用以下代码，完成其中的reorderList函数，其中形参head指向无头结点单链表。

#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:

void reorderList(ListNode* head)

{

         //填充本函数完成功能

}
1
2
3
4
5
6
7

};

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

}

void displayLink(ListNode *head)

{

ListNode *p;

p=head;

cout<<"head-->";

while(p!= NULL)

{

    cout<<p->val<<"-->";

    p=p->next;

}

cout<<"tail\n";
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

}

int main()

{

ListNode* head = createByTail();

Solution().reorderList(head);

displayLink(head);

return 0;
1
2
3
4
5
6
7

}

2.输入说明
首先输入链表长度len，然后输入len个整数，以空格分隔。
3.输出说明
输出格式见范例

4.范例
输入
5
1 2 3 4 5
输出
head–>1–>5–>2–>4–>3–>tail
5.代码实现

#include<iostream>

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:

	//2.1使用头插法进行逆转
	ListNode *reverse(ListNode *head)
	{
		if (head == NULL || head->next == NULL) return head;
		ListNode *pre = NULL,*cur=head ;
		while (cur != NULL)
		{
			ListNode *tmp = cur->next;
			cur->next = pre;
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
	//3.将两个不带头结点的单链表进行合并操作
	  ListNode *merge(ListNode *left, ListNode *right) {

		struct ListNode *dummy=(ListNode*)malloc(sizeof(ListNode));//dummy指向链表头结点
		struct ListNode *t = dummy;//t指向新链表尾部
		while (left != NULL && right != NULL) {
			t->next = left;
			t = t->next;
			left = left->next;

			t->next = right;
			t = t->next;
			right = right->next;
		}
		if (left != NULL) {
			t->next = left;
			t = t->next;
			left = left->next;

		}

		if (right != NULL) {
			t->next = right;
			t = t->next;
			right = right->next;

		}

		return dummy->next;
	}
	

	void reorderList(ListNode* head)

	{
		if (head == NULL) return;
		/*
		//1.找到中间结点【法一：计算链表长度，遍历到中间结点，但是要注意向下取整】
		struct ListNode* p = head;
		int len = 0;//计算链表长度
		while (p != NULL)
		{
			len++;
			p = p->next;
		}
	        p = head; //从头开始
		for (int i = 0; i < (len + 1) / 2 - 1; i++)
			p = p->next; 

		struct ListNode* a = p; //a指向中间结点
		struct ListNode* b = p->next;//b指向中间结点的后继
		*/
		//寻找中间结点【法二：使用快慢指针的方法，更加简单；最终指针指向的就是中间结点】
		struct ListNode *fast = head;
		struct ListNode *slow = head;

		while (fast != NULL && fast->next != NULL)
		{
			    fast = fast->next->next;//快指针每次跳两格
				slow = slow->next;//慢指针每次跳一格 
		}
		 
		struct ListNode* a = slow;
		struct ListNode* b = slow->next;

		/*
		//2.将后半部分链表进行反转【单链表的逆转写法】
		
		while (b)  //b所指开始为后半部分链表，直接在原链表进行操作
		{
			ListNode *mm = b->next; //保留b的next节点
			b->next = a;
			//cout << "b=" <<b->val<<" "<<"a="<<a->val<<endl;
			a = b, b = mm;
			
		}
		
		//3.将反转后的链表插入到原链表的前半部分

		slow->next = NULL;
		ListNode *s;
		while (head != NULL && head != a)
		{
			s = a->next;//s指向后半部分链表的第一个结点，即s==slow->next==b
			a->next = head->next;//接下来两步将a所指结点插入到head之后
			head->next = a;
			head = head->next->next;//将head指向新插入结点的后面，即head->next->next
			a = s;
		}
		*/

		
		ListNode *left = head; //第一个链表
		ListNode *right = reverse(b);//第二个链表
		slow->next = NULL;//链表尾部结点记得要置空
		head=merge(left, right);//这里head为最终的链表的头结点


	}
	

};

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;

}



void  displayLink(ListNode *head)

{

	ListNode *p;

	p = head;

	cout << "head-->";

	while (p != NULL)

	{

		cout << p->val << "-->";

		p = p->next;

	}

	cout << "tail\n";

}

int main()

{

	ListNode* head = createByTail();

	Solution().reorderList(head);

	displayLink(head);

	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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228