61.旋转链表

题目描述

原题 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
示例 1:
1
输入:head = [1,2,3,4,5], k = 2
2
输出:[4,5,1,2,3]
Copied!
示例 2:
1
输入:head = [0,1,2], k = 4
2
输出:[2,0,1]
Copied!
提示:
    链表中节点的数目在范围 [0, 500]
    -100 <= Node.val <= 100
    0 <= k <= 2 * 109

题解

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public ListNode rotateRight(ListNode head, int k) {
13
//如果元素为0或者1或者k=0 直接返回
14
if(head == null || head.next==null || k == 0) return head;
15
//优先计算链表的长度 因为k可能大于len,所以要取模
16
ListNode node = head;
17
int len = 0;
18
while(node!=null){
19
len++;
20
node = node.next;
21
}
22
k = k % len;
23
//取模计算k为0则直接返回
24
if(k == 0) return head;
25
ListNode fast = head;
26
ListNode slow = head;
27
for(int i = 0;i < k;i++){
28
fast = fast.next;
29
}
30
while(fast.next!=null){
31
fast = fast.next;
32
slow = slow.next;
33
}
34
ListNode next = slow.next;
35
slow.next = null;
36
fast.next = head;
37
return next;
38
}
39
}
Copied!
最近更新 4mo ago
复制链接