Leetcode Rotate List Problem Solution

In this Leetcode Rotate List Problem Solution Given the head of a linked list, rotate the list to the right by k places.

Leetcode Rotate List Problem Solution


Problem solution in Python.

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
 
        length = 1
        curr = head
        while curr.next:
            curr = curr.next
            length += 1
        curr.next = head
 
        for _ in range(length - k % length - 1):
            head = head.next
 
        new_head = head.next
        head.next = None
 
        return new_head

Problem solution in Java.

public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
 
        ListNode curr = head;
        int size = 0;
        while (curr != null) {
            curr = curr.next;
            size++;
        }
        
        k = k % size;
        if (size == k || k == 0) return head;
        curr = head;
        
        ListNode prev = null, fast = head, endPrev = null;;
        for (int i = 0; i < k; i++) {
            endPrev = fast;
            fast = fast.next;
        }
        
        while (fast != null) {
            prev = curr;
            endPrev = fast;
            curr = curr.next;
            fast = fast.next;
        }
        
        prev.next = null;
        endPrev.next = head;
        
        return curr;
    }


Problem solution in C++.

class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
    if(!head)   return 0;
    if(!head->next && k==0)   return head;
    ListNode *h=head,*prev,*temp=head;
    int c=1;
    while(h->next){   c++;    h=h->next;}
    k = k%c;
    if(k==0)    return head;
    c = c-k;
    while(c--)
    {
        prev = temp;
        temp = temp->next;
    }
    prev->next = NULL;
    h->next = head;
    head = temp;
    return head;
}
};


Problem solution in C.

struct ListNode* rotateRight(struct ListNode* head, int k){
 
    if(head==NULL || head->next==NULL)
        return head;
    struct ListNode* prev=NULL;
    struct ListNode* temp=NULL;
    int count=0;
    temp=head;
    while(temp!=NULL)
    {
        count++;
        temp=temp->next;
    }
    k=k%count;
    temp=head;
    while(k>0)
    {
        while(temp->next!=NULL)
        {
            prev=temp;
            temp=temp->next;
        }
        temp->next=head;
        prev->next=NULL;
        head=temp;
        temp=head;
        k=k-1;
    }
    return head;
}


Post a Comment

0 Comments