Given the head of a linked list, rotate the list to the right by k places. @param head @param k @return head of linked list
(SinglyLinkedNode head, int k)
| 82 | * @return head of linked list |
| 83 | */ |
| 84 | public SinglyLinkedNode rotateRight(SinglyLinkedNode head, int k) { |
| 85 | if (k == 0 || head == null || head.next == null) { |
| 86 | return head; |
| 87 | } |
| 88 | |
| 89 | // Finding the size of the list |
| 90 | int size = 1; // start with 1 because we're starting with head |
| 91 | SinglyLinkedNode currentEnd = head; |
| 92 | while (currentEnd.next != null) { |
| 93 | currentEnd = currentEnd.next; |
| 94 | size++; |
| 95 | } |
| 96 | |
| 97 | // linking the end to the head |
| 98 | currentEnd.next = head; |
| 99 | |
| 100 | // determine the rotation based on k |
| 101 | int rotate = 0; |
| 102 | if (k < size) { |
| 103 | rotate = k; |
| 104 | } else { |
| 105 | rotate = k % size; |
| 106 | } |
| 107 | |
| 108 | // Find the index of the end node |
| 109 | int endNode = size - rotate; |
| 110 | |
| 111 | // set the newEnd to head and loop until you get to the new end node |
| 112 | SinglyLinkedNode newEnd = head; |
| 113 | for (int i = 1; i < endNode; i++) { |
| 114 | newEnd = newEnd.next; |
| 115 | } |
| 116 | |
| 117 | // set the new head node and terminate the new end node |
| 118 | SinglyLinkedNode newHead = newEnd.next; |
| 119 | newEnd.next = null; |
| 120 | return newHead; |
| 121 | } |
| 122 | } |