61. 旋转链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 279 阅读时长 ≈ 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
class Solution {
	public:
		ListNode* rotateRight(ListNode* head, int k) {
			ListNode *dummyHead = new ListNode(-1, head), *slow = dummyHead, *fast = dummyHead, *tmp = head;
			int len = 0;
			while (tmp != nullptr) {
				tmp = tmp->next;
				len++;
			}
            //链表不为空且k求余后不为空，再做操作
			if (len && (k %= len)) {
				while (k--)	fast = fast->next;
				while (fast->next != nullptr) {
					slow = slow->next;
					fast = fast->next;
				}
				ListNode *subHead = slow->next;
				slow->next = fast->next;
				fast->next = dummyHead->next;
				dummyHead->next = subHead;
			}
			return dummyHead->next;
		}
};

思路

根据题意，假设链表{1, 2, 3, 4, 5}右移3个单位，很容易想到

故而先求整个链表的长度，然后让K对它取余，就能得到需要移动的子链表长度

假设整个链表长度为5，子链表长度也为5，那么子链表就是整体链表，就不需要移动

然后使用快慢指针找到子链表的dummyHead、头节点和尾节点后，更改位置即可

当然，你也可以把链表连接成环，同样使用快慢指针找到子链表的dummyHead与头节点并断开形成新链表，时间复杂度是一样的，你可以尝试一下~