Joyce' Blog
0%

reverse-linked-list-ii

发表于 更新于

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。1 ≤ m ≤ 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
ListNode* reverseBetween(ListNode* head, int m, int n) {
	if (m == n)return head;
	ListNode* prehead = new ListNode(0);
	prehead->next = head;
	int i = m;
	ListNode* front = prehead;
	while (i)
	{
		front = front->next;
		i--;
	}
	stack<int> s;
	ListNode* back;
	back = front;
	int k = n - m;
	while (k)
	{
		s.push(back->val);
		back = back->next;
		k--;
	}
	s.push(back->val);
	while (!s.empty())
	{
		front->val = s.top();
		s.pop();
		front = front->next;
	}
	return prehead->next;
}

看到官方题解里还有一些其他思路：

递归

对于反转字符串，可以创建两个指针，一个开头，一个结尾。不断地交换这两个指针指向的元素，并将两个指针向中间移动。但是对于反转链表，链表中没有向后指针，也没有下标。因此，我们需要使用递归来 模拟 向后指针。递归中的回溯可以帮助我们模拟一个指针从第n个结点向中心移动的移动过程。

反转指针