/*
This implementation demonstrates how to
efficiently shift a singly linked list
in place by k positions.
Example:
shifting 0-> 1 -> 2 -> 3 -> 4-> null
by 2 positions yields:
3 -> 4 -> 0 -> 1 -> 2 -> null
Let n be the number of nodes in the list.
Time complexity: O(n)
Space complexity: O(1)
*/
public class LinkedListShifting {
private ListNode head;
public LinkedListShifting() {
/*
* Create below linked list
* 0 -> 1 -> 2 -> 3 -> 4 -> null
*/
head = new ListNode(0, null);
ListNode prev = head, temp;
for (int i = 1; i <= 4; i++) {
temp = new ListNode(i, null);
prev.next = temp;
prev = temp;
}
}
public static void main(String[] args) {
LinkedListShifting application = new LinkedListShifting();
application.head = application.shiftLinkedList(2);
System.out.println(application.head.val); // 3
}
public ListNode shiftLinkedList(int k) {
if (head == null) {
return null;
}
int length = 1;
ListNode listTail = head;
// Count the number of list nodes
while (listTail.next != null) {
listTail = listTail.next;
length++;
}
// The offset should less than length
int offset = Math.abs(k) % length;
if (offset == 0)
return head; // no shifting is needed
int newTailPosition = k > 0 ? length - offset : offset;
ListNode newTail = head;
for (int i = 1; i < newTailPosition; i++) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
listTail.next = head;
return newHead;
}
// Class representing a linked list node
// with pointers to value and next node
private class ListNode {
int val;
ListNode next;
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
def rotate(self, k):
if self.head and self.head.next:
p = self.head
q = self.head
prev = None
count = 0
while p and count < k:
prev = p
p = p.next
q = q.next
count += 1
p = prev
while q:
prev = q
q = q.next
q = prev
q.next = self.head
self.head = p.next
p.next = None