Interview Question

    Linked List Rotation

Given a linked list and a number n, rotate the linked list by n places.  Submit your answer as pseudocode to fit as indicated below:

class Node {
  def __init__(self, val, next=None) {
      self.val = val
      self.next = next
  }
  def __str__(self) {
      current = self
      ret = ''
      while current {
         ret += str(current.val)
         current = current.next
  }
}
def rotate_llist(llist, n) {
     # YOUR ANSWER HERE
}
llist = Node(1, Node(2, Node(3, Node(4))))
print(rotate_llist(llist, 2));
# 3412

 


Answers

  • ▲
    1024
    ▼ 

    llist = Node(1, Node(2, Node(3, Node(4))))
print(rotate_llist(llist, 2));

  • ▲
    256
    ▼
    @paul.n.xavier 

    if n == 0:
    return
count = 1
head=llist
#increment count to the new head
while(count < n and llist is not None)
      llist = llist.next
      count += 1
#assign the new head
newHead = llist
newHead.next=None
#traverse till end of list
while(llist is not None)
      llist = llist.next
llist.next=head

  • ▲
    256
    ▼
    @ggetsin 

    current = self
int index = 0;
while  current && index < n { 
  current = current.next
  index++
}

  • ▲
    192
    ▼ 

    def rotate_llist(llist, n):
    if (n<=0 or n%4==0):
        return llist
    j=0
    newList = llist
    while(j < (n%4)):
        newList = newList.next
        j+=1
    
    temp = llist
    current = temp
    i = 0
    while (i < ((n-1)%4)):
        current = current.next
        i+=1
    current.next = None
    
    newCurrent = newList
    while(newCurrent.next != None):
        newCurrent = newCurrent.next
    newCurrent.next = temp
    return newList

  • ▲
    128
    ▼
    @shalabh.neema 

    
Node start=llist

for(int i=0;i<n-1;i++)
lllist=llist.next;

Node newstart=llist.next;
llist.next==null;

Node temp=newstart;
(temp!=null)
tenp=temp.next;

temp.next=start;
return newstart;

Interview Questions

This question was recently asked at a major tech company (ie Google, Apple, Facebook, Amazon)
We're compiling a definitive list of interview questions.

Take a practice interview and score yourself.

<< Return to Index