3 votes 3 votes Time complexity of the optimal algorithm to interchange the $m^{th}$ and $n^{th}$ elements of a singly Linked List is $\Theta(m+n)$ $\Theta(m)$ when $m\geq n$ otherwise $\Theta(n)$ $\Theta(m)$ if $m \leq n$ otherwise $\Theta(n)$ $\Theta(m+ \min (m,n))$ Algorithms go-alogrithms-1 algorithms linked-list + – Bikram asked Oct 4, 2016 Bikram 636 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 7 votes 7 votes To interchange the mth and nth elements of a singly Linked List we have to fetch each mth and nth element. amd then swap. Complexity will be O(max (m,n)) for searching and O(1) for swapping. O(max(m,n)) Digvijay Pandey answered Oct 11, 2016 • selected Oct 11, 2016 by Arjun Digvijay Pandey comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments kamakshi commented Oct 28, 2017 reply Follow Share Difference between option a and b? 0 votes 0 votes shraddha priya commented Mar 19, 2019 reply Follow Share @Tesla!! But are we changing the links of these two nodes of linked lists or just the value of variables inside them?! 0 votes 0 votes Tesla! commented Mar 20, 2019 reply Follow Share @shraddha priya you can change link as well as value it doesn't matter 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Say m < n. Traverse up to m. Introduce a duplicate pointer from there, and traverse up to n. Swap values using some temporary variable. Hence, it takes O(n) time, when n>m So, Option B. Option A is also correct. https://stackoverflow.com/questions/19455942/understanding-time-complexity-of-omaxm-n JashanArora answered Dec 14, 2019 JashanArora comment Share Follow See all 0 reply Please log in or register to add a comment.