Permalink
Cannot retrieve contributors at this time
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
# Time: O[n] | |
# Space: O[1] | |
# | |
# Given a list, rotate the list to the right by k places, where k is non-negative. | |
# | |
# For example: | |
# Given 1->2->3->4->5->NULL and k = 2, | |
# return 4->5->1->2->3->NULL. | |
# | |
# 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 | |
if __name__ == "__main__": | |
head = ListNode[1] | |
head.next = ListNode[2] | |
head.next.next = ListNode[3] | |
head.next.next.next = ListNode[4] | |
head.next.next.next.next = ListNode[5] | |
print Solution[].rotateRight[head, 2] |
Homecoding problemsLeetcode Rotate List problem solution
In this Leetcode Rotate List problem solution we have given the head of a linked list, rotate the list to the right by k places.
Problem solution in Python.
class Solution: def rotateRight[self, head: ListNode, k: int] -> ListNode: if head == None: return values = [] dummay = ListNode[] cur = dummay while head: values.append[head.val] head = head.next for i in range[k % len[values]]: values.insert[0,values.pop[]] for j in values: cur.next = ListNode[j] cur = cur.next return dummay.next
Problem solution in Java.
public class Solution { public ListNode rotateRight[ListNode head, int k] { if[head == null || head.next == null] return head; ListNode p = head; int count = 1; while[p.next!= null]{ count++; p = p.next; } k = k % count; p.next = head; /*make a circle here*/ p = head; for[int i = 0; i < count - k - 1; i++]{ p = p.next; } ListNode dummy = p.next; p.next = null; return dummy; } }
Problem solution in C++.
class Solution { public: ListNode* rotateRight[ListNode* head, int k] { if[head == NULL || head->next == NULL] return head; int nodes = 1; ListNode *temp = head; while[temp->next != NULL]{ temp = temp->next; nodes++; } k = k % nodes; if[k == 0]return head; int i = 0; ListNode *cur = head; while[inext; i++; } ListNode *newHead = cur->next; temp->next = head; cur->next = NULL; return newHead; } };
Problem solution in C.
struct ListNode* rotateRight[struct ListNode* head, int k]{ int length = 0; struct ListNode* tmp; struct ListNode* tmp2; tmp = head; while [tmp] { length++; tmp2 = tmp; tmp = tmp->next; } if [length == 0] { return head; } k = k % length; tmp = head; for [int i = 0; i < length - k - 1; i++] { tmp = tmp->next; } tmp2->next = head; head = tmp->next; tmp->next = NULL; return head; }