LeetCode刷题实战61:旋转链表
共 1703字,需浏览 4分钟
·
2020-10-11 12:38
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 旋转链表,我们先来看题面:
https://leetcode-cn.com/problems/rotate-list/
Given a linked list, rotate the list to the right by k places, where k is non-negative.
题意
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
解题
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
int count = 1;
ListNode cur = head;
while (cur.next != null) {
count++;
cur = cur.next;
}
k = k % count;
if (k == 0) {
return head;
}
cur.next = head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < count - k; i++) {
prev = prev.next;
}
cur = prev.next;
prev.next = null;
return cur;
}
}
上期推文: