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 :
Input: 1->2->3->4 Output: 1->3->2->4 Input: 11->15->20->5->10 Output: 11->20->5->15->10
A simple approach to do this, is to sort the linked list using merge sort and then swap alternate, but that requires O(n Log n) time complexity. Here n is number of elements in linked list.
An efficient approach 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 for detailed explanation of swapping order.
C++ programming:
[pastacode lang=”cpp” manual=”%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” message=”” highlight=”” provider=”manual”/]Output :
Given linked list 4->3->7->8->6->2->1->NULL Zig Zag Linked list 3->7->4->8->2->6->1->NULL
In 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.
Time complexity : O(n)
Auxiliary Space : O(1)