How do you rotate a list by moving each element in the list n times to the right?

Rotate a Linked List

Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer. For example, if the given linked list is 10->20->30->40->50->60 and k is 4, the list should be modified to 50->60->10->20->30->40. Assume that k is smaller than the count of nodes in a linked list.

Leetcode: Given a list, rotate the list to the right by k places.

//leetcode.com/problems/rotate-list

Consider example 1->2->3->4 rotate the list by 2. 3->4->1->2.

I have explained two different approaches. Each method has code sample with comments to understand it easily.

The LinkedList for the example is singly. Here is how Node class looks like:

class Node { int value; protected Node next; public Node(int value) { this.value = value; } public int getValue() { return value; } }

Method 1. (more intutive)

public class RotateLinkedList { public ListNode reverseKList(ListNode head, int k) { ListNode temp = head; int count =0; while(temp !=null) { count++; temp = temp.next; } //if k is greater than the length of the list, the take a mod k = k > count ? k%count:k; return reverseList(head, k); } private ListNode reverseList(ListNode head, int length) { ListNode prev = null; ListNode first = head; ListNode temp = null; int i = length; if(length == 0) return head; //reverse k elements while(i-- > 0 && head != null) { temp = head.next; head.next = prev; prev = head; head = temp; } // now temp is pointing to k+1, call reverseList recursively // first is the first element of k list, which will now be // the last element of k list, since its reversed. if(temp != null) { first.next = reverseList(temp, length); } //prev is now the first element of the reversed list return prev; } public static void main(String[] args) { ListNode l = new ListNode(1); ListNode l1 = new ListNode(2); ListNode l2 = new ListNode(3); ListNode l3 = new ListNode(4); ListNode l4 = new ListNode(5); l.next = l1;l1.next=l2;l2.next=l3;l3.next=l4; System.out.println("Original List"); ListNode n = l; while(n != null) { System.out.print(n.val +" "); n=n.next; } System.out.println(""); //reverse by k n = new ReverseListK().reverseKGroup(l, 4); System.out.println("New List: "); while(n != null) { System.out.print(n.val +" "); n=n.next; } } } Output: Original List 1 2 3 4 5 New List: 4 3 2 1 5

Method 2

There is an easier and faster approach.

• Traverse the list till the end. Keep the counter for length n
• Connect the end of list to the start. Continue traversing from last element
• Continue traversing till n-k
• the n-k element will be the last element of new list , n-k+1 will be the first element of the list
• traverse to n-k+1 and set the next of n-k element to NULL

public ListNode rotateRight(ListNode head, int k) { int count = 0; ListNode start = head; //traverse till the end of the list and keep incrementing //count while (head.next != null) { head = head.next; count++; } count++; // if k > count, do k%count, its an optimization. 2%5 == 12%5 k = k % count; //find the new k k = Math.abs(count - k); if (k == 0) return start; //connect last element to start head.next = start; //traverse for new k value while (k-- > 0) { head = head.next; } // note: head is not the last element, so set the start. start = head.next; head.next = null; return start;

Please enable JavaScript to view the comments powered by Disqus.

How do you rotate a list by moving each element in the list n times to the right using Java?

Method 2

1. Traverse the list till the end. Keep the counter for length n.
2. Connect the end of list to the start.
3. Continue traversing till n-k.
4. the n-k element will be the last element of new list , n-k+1 will be the first element of the list.
5. traverse to n-k+1 and set the next of n-k element to NULL.

How do you rotate an element in a list in Python?

Rotate a Python list

1. Using deque rotate() function. The collections.
2. Using numpy.roll() function. If you happen to be using NumPy already, you can use the roll() function that rotates the array elements along a given axis.
3. Using Slicing.

What are the Efficient ways to rotate a List in Python?

In this article, we will learn to rotate a list in Python. We will use some built-in functions, simple approaches, and some custom codes as well. Let's first have a quick look over what is a list in Python.

1. Rotating k times

The idea is to right-rotate all array elements by one position k times, where k is the given rotation count. This approach is demonstrated below in C, Java, and Python:

C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <stdio.h> // Function to right-rotate an array by one position void rightRotateByOne(int A[], int n) { int last = A[n - 1]; for (int i = n - 2; i >= 0; i--) { A[i + 1] = A[i]; } A[0] = last; } // Function to right-rotate an array by `k` positions void rightRotate(int A[], int k, int n) { // base case: invalid input if (k < 0 || k >= n) { return; } for (int i = 0; i < k; i++) { rightRotateByOne(A, n); } } int main(void) { int A[] = { 1, 2, 3, 4, 5, 6, 7 }; int k = 3; int n = sizeof(A)/sizeof(A[0]); rightRotate(A, k, n); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } return 0; }

DownloadRun Code

Output:

5, 6, 7, 1, 2, 3, 4

Approach for Rotate List Leetcode Solution

The problem Rotate List Leetcode Solution states that you are given a linked list with an integer for rotation. This means that we need to rotate the list k places to the right. The problem can be understood by a simple operation of taking the elements from the end of the list and placing them in front. Since there is no way to efficiently remove an element from the end and place it in front. We need to think of any other way to perform the operation. If we observe, we can see that after performing k operations, k elements from the end are removed and are placed in front. One thing to note here is, if the size of k is greater than the size of the linked list. We will take the modulo of k over the length of the linked list.

See also

Contiguous Array Leetcode

Once done, we will traverse until the kth node from the end. Then we perform some of the operations, we assign the next of the last node to the head. Assign the kth node from the end as head of the linked list. But we should not forget assigning the next node of k-1 th node from the end as null. Now, after performing these 3 operations, we have rotated the list.

Code for Rotate List Leetcode Solution

C++ code

#include <bits/stdc++.h> using namespace std; struct ListNode{ int data; ListNode* next; }; ListNode* rotateRight(ListNode* head, int k) { if(head==NULL || head->next==NULL)return head; ListNode *tmp = head; int cnt = 0; while(tmp)tmp=tmp->next,cnt++; tmp=head; k%=cnt; if(k==0)return head; while(k--)tmp = tmp->next; ListNode *tmpHead = head; while(tmp->next!=NULL){ tmp = tmp->next; head = head->next; } ListNode* newHead = head->next; tmp->next = tmpHead; head->next = NULL; return newHead; } int main(){ ListNode *head = new ListNode(); head->data = 0; head->next = new ListNode(); head->next->data = 1; head->next->next = new ListNode(); head->next->next->data = 2; head = rotateRight(head, 4); while(head != NULL){ cout<<head->data<<" "; head = head->next; } } 2 0 1

Java Code

import java.util.*; import java.lang.*; import java.io.*; class ListNode{ int data; ListNode next; } class Solution { public static ListNode rotateRight(ListNode head, int k) { if(head==null || head.next==null)return head; ListNode tmp = head; int cnt = 0; while(tmp != null){ tmp=tmp.next; cnt++; } tmp=head; k %= cnt; if(k==0)return head; while(k-- > 0) tmp = tmp.next; ListNode tmpHead = head; while(tmp.next != null){ tmp = tmp.next; head = head.next; } ListNode newHead = head.next; tmp.next = tmpHead; head.next = null; return newHead; } public static void main(String[] args){ ListNode head = new ListNode(); head.data = 0; head.next = new ListNode(); head.next.data = 1; head.next.next = new ListNode(); head.next.next.data = 2; head = rotateRight(head, 4); while(head != null){ System.out.print(head.data + " "); head = head.next; } } }2 0 1