Given a linked list, rearrange it such that converted list should be of the form a < b > c < d > e < f .. where a, b, c.. are consecutive data node of linked list. Examples :<\/p>\n
Input: 1->2->3->4\r\nOutput: 1->3->2->4 \r\n\r\nInput: 11->15->20->5->10\r\nOutput: 11->20->5->15->10\r\n\r\n<\/pre>\nA simple approach<\/strong> to do this, is to sort the linked list using merge sort<\/a> and then swap alternate, but that requires O(n Log n) time complexity. Here n is number of elements in linked list.<\/p>\n
An efficient approach<\/strong> which requires O(n) time is, using a single scan similar to bubble sort and then maintain a flag for representing which order (< or >) currently we are. If the current two elements are not in that order then swap those elements otherwise not. Please refer this<\/a> for detailed explanation of swapping order.<\/p>\n
C++ programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20arrange%20linked%20list%20in%20zigzag%20fashion%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20Link%20list%20Node%20*%2F%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20Node*%20next%3B%0A%7D%3B%0A%20%0A%2F%2F%20This%20function%20distributes%20the%20Node%20in%20zigzag%20fashion%0Avoid%20zigZagList(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20If%20flag%20is%20true%2C%20then%20next%20node%20should%20be%20greater%0A%20%20%20%20%2F%2F%20in%20the%20desired%20output.%0A%20%20%20%20bool%20flag%20%3D%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20linked%20list%20starting%20from%20head.%0A%20%20%20%20Node*%20current%20%3D%20head%3B%0A%20%20%20%20while%20(current-%3Enext%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(flag)%20%20%2F*%20%22%3C%22%20relation%20expected%20*%2F%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20we%20have%20a%20situation%20like%20A%20%3E%20B%20%3E%20C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20where%20A%2C%20B%20and%20C%20are%20consecutive%20Nodes%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20in%20list%20we%20get%20A%20%3E%20B%20%3C%20C%20by%20swapping%20B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20and%20C%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(current-%3Edata%20%3E%20current-%3Enext-%3Edata)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swap(current-%3Edata%2C%20current-%3Enext-%3Edata)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%20%2F*%20%22%3E%22%20relation%20expected%20*%2F%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20we%20have%20a%20situation%20like%20A%20%3C%20B%20%3C%20C%20where%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A%2C%20B%20and%20C%20%20are%20consecutive%20Nodes%20in%20list%20we%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20get%20A%20%3C%20C%20%3E%20B%20by%20swapping%20B%20and%20C%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(current-%3Edata%20%3C%20current-%3Enext-%3Edata)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20swap(current-%3Edata%2C%20current-%3Enext-%3Edata)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20flag%20%3D%20!flag%3B%20%20%2F*%20flip%20flag%20for%20reverse%20checking%20*%2F%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20push%20a%20Node%20*%2F%0Avoid%20push(Node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20Node%20*%2F%0A%20%20%20%20struct%20Node*%20new_Node%20%3D%20new%20Node%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_Node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20Node%20*%2F%0A%20%20%20%20new_Node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20Node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_Node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20linked%20list%20*%2F%0Avoid%20printList(struct%20Node%20*Node)%0A%7B%0A%20%20%20%20while%20(Node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d-%3E%22%2C%20Node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20Node%20%3D%20Node-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22NULL%22)%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main(void)%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20Node*%20head%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F%2F%20create%20a%20list%204%20-%3E%203%20-%3E%207%20-%3E%208%20-%3E%206%20-%3E%202%20-%3E%201%0A%20%20%20%20%2F%2F%20answer%20should%20be%20-%3E%203%20%207%20%204%20%208%20%202%20%206%20%201%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%202)%3B%0A%20%20%20%20push(%26head%2C%206)%3B%0A%20%20%20%20push(%26head%2C%208)%3B%0A%20%20%20%20push(%26head%2C%207)%3B%0A%20%20%20%20push(%26head%2C%203)%3B%0A%20%20%20%20push(%26head%2C%204)%3B%0A%20%0A%20%20%20%20printf(%22Given%20linked%20list%20%5Cn%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20zigZagList(head)%3B%0A%20%0A%20%20%20%20printf(%22%5CnZig%20Zag%20Linked%20list%20%5Cn%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20return%20(0)%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output :<\/strong><\/p>\n
Given linked list \r\n4->3->7->8->6->2->1->NULL\r\n\r\nZig Zag Linked list \r\n3->7->4->8->2->6->1->NULL<\/pre>\nIn above code, push function pushes the node at the front of the linked list, the code can be easily modified for pushing node at the end of list. Other thing to note is, swapping of data between two nodes is done by swap by value not swap by links for simplicity, for swap by links technique please see this<\/a>.<\/p>\n
Time complexity : O(n)
\nAuxiliary Space : O(1)<\/p>\n","protected":false},"excerpt":{"rendered":"Cpp Algorithm-Rearrange a Linked List in Zig-Zag fashion-Linked list
\nGiven a linked list, rearrange it such that converted list should be <\/p>\n","protected":false},"author":1,"featured_media":31287,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81795,81927,81933,81926,81934,81935,81936,81929,81931,81930,81932,81928],"class_list":["post-27648","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-linked-list","category-singly-linked-list","tag-add-1-to-a-number-represented-as-linked-list","tag-delete-nodes-having-greater-value-on-right","tag-even-odd-linked-list","tag-rearrange-linkedin-list","tag-reorder-linked-list","tag-reorder-linkedin","tag-reorder-list","tag-tortoise-and-hare-method","tag-zigzag-array-algorithm","tag-zigzag-array-hackerrank-solution-java","tag-zigzag-array-in-java","tag-zigzag-matrix-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27648","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27648"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27648\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31287"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27648"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27648"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27648"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}