top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Given a singly linked list: 1->2->3->4->5, Change it to 1->5->2->4->3 using O(1) space?

0 votes
317 views
Given a singly linked list: 1->2->3->4->5, Change it to 1->5->2->4->3 using O(1) space?
posted Dec 10, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

If we know the total number of element in the list, then prepare two list half and half.

First Half :- 1->2->3
Second Half -> 4->5

Then Reverse the second which will be 5->4;

Then you can merge the list with first list pointer moving each time two times, and second pointer one time.
1->5>2->4->3;
O(1) space is nothing but constant space, so you are allocating just some pointers to reverse the linked list and one pointer to point the new list .

answer Dec 14, 2016 by Sachidananda Sahu
...