25. K 个一组翻转链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 336 阅读时长 ≈ 1 分钟

考点

  • 链表的反转

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
	public:
		ListNode* reverseKGroup(ListNode* head, int k) {
			ListNode *dummyHead = new ListNode(-1, head), *subDummyHead = dummyHead;
			while (subDummyHead->next != nullptr) {
				ListNode *tmp = subDummyHead;
				int i = 0;
				for (; i < k && tmp != nullptr; i++) tmp = tmp->next;
				if (tmp == nullptr) break;
				//使用改进版头插法进行反转子链表
				ListNode *tail = subDummyHead->next;
				while (--i) {
					ListNode *node = tail->next;
					tail->next = node->next;
					node->next = subDummyHead->next;
					subDummyHead->next = node;
				}
				subDummyHead = tail;
			}
			return dummyHead->next;
		}
};

思路

凡是链表翻转类的题目，使用改进版头插法就对了，详见206. 反转链表

因为题目是要求每次翻转长度为K的子链表，除了要在子链表头前再找一个节点作为dummyHead外，每次还要先判断子链表长度是不是K

每次翻转结束后，当前子链表的尾节点恰好就是下一组子链表的dummyHead，从而开启新一轮的翻转

其余代码套改进版头插法的模板就好了

这里改成递归也行，但是和迭代没太大区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
	private:
		void recursiveFunc(ListNode* subDummyHead, int k) {
			ListNode *tmp = subDummyHead;
			int i = 0;
			for (; i < k && tmp != nullptr; i++) tmp = tmp->next;
			if (tmp == nullptr) return;
			//使用改进版头插法进行反转子链表
			ListNode *tail = subDummyHead->next;
			while (--i) {
				ListNode *node = tail->next;
				tail->next = node->next;
				node->next = subDummyHead->next;
				subDummyHead->next = node;
			}
			recursiveFunc(tail, k);
		}
	public:
		ListNode* reverseKGroup(ListNode* head, int k) {
			ListNode *dummyHead = new ListNode(-1, head);
			recursiveFunc(dummyHead, k);
			return dummyHead->next;
		}
};