[LeetCode] 61. Rotate List 旋转链表

时间:2023-02-04 17:10:49

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

189. Rotate Array类似,但链表不能通过index来访问,要一步步的走,所以要麻烦一些。

要注意当k大于链表长度时的处理,需要先遍历一遍得到链表长度n,然后k对n取余,用余数来翻转。

Java:

public ListNode rotateRight(ListNode head, int n) {
if (head==null||head.next==null) return head;
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode fast=dummy,slow=dummy; int i;
for (i=0;fast.next!=null;i++)//Get the total length
fast=fast.next; for (int j=i-n%i;j>0;j--) //Get the i-n%i th node
slow=slow.next; fast.next=dummy.next; //Do the rotation
dummy.next=slow.next;
slow.next=null; return dummy.next;
}  

Python:

# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None def __repr__(self):
if self:
return "{} -> {}".format(self.val, repr(self.next)) class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or not head.next:
return head n, cur = 1, head
while cur.next:
cur = cur.next
n += 1
cur.next = head cur, tail = head, cur
for _ in xrange(n - k % n):
tail = cur
cur = cur.next
tail.next = None return cur 

C++:

class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if (!head) return NULL;
int n = 0;
ListNode *cur = head;
while (cur) {
++n;
cur = cur->next;
}
k %= n;
ListNode *fast = head, *slow = head;
for (int i = 0; i < k; ++i) {
if (fast) fast = fast->next;
}
if (!fast) return head;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
fast->next = head;
fast = slow->next;
slow->next = NULL;
return fast;
}
};

C++:

class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if (!head) return NULL;
int n = 1;
ListNode *cur = head;
while (cur->next) {
++n;
cur = cur->next;
}
cur->next = head;
int m = n - k % n;
for (int i = 0; i < m; ++i) {
cur = cur->next;
}
ListNode *newhead = cur->next;
cur->next = NULL;
return newhead;
}
};

  

  

类似题目:

[LeetCode] 189. Rotate Array 旋转数组

[LeetCode] 48. Rotate Image 旋转图像

All LeetCode Questions List 题目汇总