Hướng dẫn 61. rotate list python

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;
}