第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0061. 旋转链表
题目地址(61. 旋转链表)
题目描述
1
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
2
3
示例 1:
4
5
输入: 1->2->3->4->5->NULL, k = 2
6
输出: 4->5->1->2->3->NULL
7
解释:
8
向右旋转 1 步: 5->1->2->3->4->NULL
9
向右旋转 2 步: 4->5->1->2->3->NULL
10
示例 2:
11
12
输入: 0->1->2->NULL, k = 4
13
输出: 2->0->1->NULL
14
解释:
15
向右旋转 1 步: 2->0->1->NULL
16
向右旋转 2 步: 1->2->0->NULL
17
向右旋转 3 步: 0->1->2->NULL
18
向右旋转 4 步: 2->0->1->NULL
Copied!
快慢指针法
前置知识
- 求单链表的倒数第 N 个节点
思路一
- 1.采用快慢指
- 2.快指针与慢指针都以每步一个节点的速度向后遍历
- 3.快指针比慢指针先走 N 步
- 4.当快指针到达终点时，慢指针正好是倒数第 N 个节点
思路一代码
- 伪代码
1
快指针 = head;
2
慢指针 = head;
3
while (快指针.next) {
4
if (N-- <= 0) {
5
慢指针 = 慢指针.next;
6
}
7
快指针 = 快指针.next;
8
}
Copied!
- 语言支持: JS
JS Code:
1
let slow = (fast = head);
2
while (fast.next) {
3
if (k-- <= 0) {
4
slow = slow.next;
5
}
6
fast = fast.next;
7
}
Copied!
思路二
- 1.获取单链表的倒数第 N + 1 与倒数第 N 个节点
- 2.将倒数第 N + 1 个节点的 next 指向 null
- 3.将链表尾节点的 next 指向 head
- 4.返回倒数第 N 个节点
例如链表 A -> B -> C -> D -> E 右移 2 位，依照上述步骤为：
- 1.获取节点 C 与 D
- 2.A -> B -> C -> null, D -> E
- 3.D -> E -> A -> B -> C -> nul
- 4.返回节点 D
注意：假如链表节点长度为 len， 则右移 K 位与右移动 k % len 的效果是一样的 就像是长度为 1000 米的环形跑道， 你跑 1100 米与跑 100 米到达的是同一个地点
思路二代码
- 伪代码
1
获取链表的长度
2
k = k % 链表的长度
3
获取倒数第k + 1,倒数第K个节点与链表尾节点
4
倒数第k + 1个节点.next = null
5
链表尾节点.next = head
6
return 倒数第k个节点
Copied!
- 语言支持: JS, JAVA, Python, CPP, Go, PHP
JS Code:
1
var rotateRight = function (head, k) {
2
if (!head || !head.next) return head;
3
let count = 0,
4
now = head;
5
while (now) {
6
now = now.next;
7
count++;
8
}
9
k = k % count;
10
let slow = (fast = head);
11
while (fast.next) {
12
if (k-- <= 0) {
13
slow = slow.next;
14
}
15
fast = fast.next;
16
}
17
fast.next = head;
18
let res = slow.next;
19
slow.next = null;
20
return res;
21
};
Copied!
JAVA Code:
1
class Solution {
2
public ListNode rotateRight(ListNode head, int k) {
3
if(head == null || head.next == null) return head;
4
int count = 0;
5
ListNode now = head;
6
while(now != null){
7
now = now.next;
8
count++;
9
}
10
k = k % count;
11
ListNode slow = head, fast = head;
12
while(fast.next != null){
13
if(k-- <= 0){
14
slow = slow.next;
15
}
16
fast = fast.next;
17
}
18
fast.next = head;
19
ListNode res = slow.next;
20
slow.next = null;
21
return res;
22
}
23
}
Copied!
Python Code:
1
class Solution:
2
def rotateRight(self, head: ListNode, k: int) -> ListNode:
3
# 双指针
4
if head:
5
p1 = head
6
p2 = head
7
count = 1
8
i = 0
9
while i < k:
10
if p2.next:
11
count += 1
12
p2 = p2.next
13
else:
14
k = k % count
15
i = -1
16
p2 = head
17
i += 1
18
19
while p2.next:
20
p1 = p1.next
21
p2 = p2.next
22
23
if p1.next:
24
tmp = p1.next
25
else:
26
return head
27
p1.next = None
28
p2.next = head
29
return tmp
Copied!
CPP Code:
1
class Solution {
2
int getLength(ListNode *head) {
3
int len = 0;
4
for (; head; head = head->next, ++len);
5
return len;
6
}
7
public:
8
ListNode* rotateRight(ListNode* head, int k) {
9
if (!head) return NULL;
10
int len = getLength(head);
11
k %= len;
12
if (k == 0) return head;
13
auto p = head, q = head;
14
while (k--) q = q->next;
15
while (q->next) {
16
p = p->next;
17
q = q->next;
18
}
19
auto h = p->next;
20
q->next = head;
21
p->next = NULL;
22
return h;
23
}
24
};
Copied!
Go Code:
1
/**
2
* Definition for singly-linked list.
3
* type ListNode struct {
4
* Val int
5
* Next *ListNode
6
* }
7
*/
8
func rotateRight(head *ListNode, k int) *ListNode {
9
if head == nil || head.Next == nil {
10
return head
11
}
12
n := 0
13
p := head
14
for p != nil {
15
n++
16
p = p.Next
17
}
18
k = k % n
19
// p 为快指针, q 为慢指针
20
p = head
21
q := head
22
for p.Next!=nil {
23
p = p.Next
24
if k>0 {
25
k--
26
} else {
27
q = q.Next
28
}
29
}
30
// 更新指针
31
p.Next = head
32
head = q.Next
33
q.Next = nil
34
35
return head
36
}
Copied!
PHP Code:
1
/**
2
* Definition for a singly-linked list.
3
* class ListNode {
4
* public $val = 0;
5
* public $next = null;
6
* function __construct($val) { $this->val = $val; }
7
* }
8
*/
9
class Solution
10
{
11
12
/**
13
* @param ListNode $head
14
* @param Integer $k
15
* @return ListNode
16
*/
17
function rotateRight($head, $k)
18
{
19
if (!$head || !$head->next) return $head;
20
21
$p = $head;
22
$n = 0;
23
while ($p) {
24
$n++;
25
$p = $p->next;
26
}
27
$k = $k % $n;
28
$p = $q = $head; // $p 快指针; $q 慢指针
29
while ($p->next) {
30
$p = $p->next;
31
if ($k > 0) $k--;
32
else $q = $q->next;
33
}
34
$p->next = $head;
35
$head = $q->next;
36
$q->next = null;
37
38
return $head;
39
}
40
}
Copied!
复杂度分析
- 时间复杂度：节点最多只遍历两遍，时间复杂度为$O(N)$
- 空间复杂度：未使用额外的空间，空间复杂度$O(1)$
最近更新 1yr ago