{"id":1823,"date":"2020-06-11T18:57:13","date_gmt":"2020-06-11T18:57:13","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1823"},"modified":"2022-11-22T09:49:05","modified_gmt":"2022-11-22T09:49:05","slug":"reorder-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/reorder-list\/","title":{"rendered":"REORDER LIST"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we will discuss different approaches to reorder linked list. Reordering a linked list will always clear the topic like a linked list. And Having knowledge about linked list will make your data structures strong.<\/p>\n

How to Reorder List<\/h2>\n
\n

Given a singly linked list L:L0\u2192L1\u2192\u2026\u2192Ln\u22121\u2192Ln<\/code>,
\nreorder it to :L0\u2192Ln\u2192L1\u2192Ln\u22121\u2192L2\u2192Ln\u22122\u2192\u2026<\/code>
\nYou must do this in-place without altering the nodes\u2019 values.
\nExpected Time Complexity O(<\/code>n)<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Example:<\/strong><\/p>\n

 Given 1->2->3->4,\n  reorder it to 1->4->2->3.<\/code><\/pre>\n
Approaches to Reorder List<\/h2>\n
Approach 1(Brute force) To Reorder The Given Linked List:<\/h3>\n
\n
1) Initialize the current node as head.<\/p>\n
2) While next of current node is not null,find the last node, remove it from the end and insert it as next of the current node.<\/p>\n
3) Move current to next of current.<\/p>\n
TIME COMPLEXITY:<\/strong> O(<\/code>n*n)<\/code><\/p>\n<\/blockquote>\n
Approach 2 (Efficient solution) To Reorder The Given Linked List:<\/h3>\n
\n
This approach uses two pointers(tortoise and hare method) to find the middle of linked list.Reverse the second half and alternately merge the first and second halves.<\/p>\n<\/blockquote>\n
Approach 3 (Deque) To Reorder The Given Linked List:<\/h3>\n
\n
1) Create an empty deque.<\/p>\n
2) Insert all elements from the linked list to the deque.<\/p>\n
3) Insert the element back to the linked list from deque in alternate fashion i.e first then last and so on.<\/p>\n<\/blockquote>\n
Code implementations<\/h2>\n\t\t\t\t\t\t