{"id":27596,"date":"2018-04-04T19:33:16","date_gmt":"2018-04-04T14:03:16","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27596"},"modified":"2018-04-04T19:33:16","modified_gmt":"2018-04-04T14:03:16","slug":"java-algorithm-pairwise-swap-elements-given-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-pairwise-swap-elements-given-linked-list\/","title":{"rendered":"Java Algorithm &#8211; Pairwise swap elements of a given linked list"},"content":{"rendered":"<p>Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.<span id=\"more-7049\"><\/span><\/p>\n<div id=\"practice\">\u00a0<strong>METHOD 1 (Iterative) <\/strong><br \/>\nStart from the head node and traverse the list. While traversing swap data of each node with its next node\u2019s data<\/div>\n<div><\/div>\n<div><strong>Java Programming:<\/strong><\/div>\n<div>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20pairwise%20swap%20elements%20of%20a%20linked%20list%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2F%20head%20of%20list%0A%20%20%0A%20%20%20%20%2F*%20Linked%20list%20Node*%2F%0A%20%20%20%20class%20Node%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%3B%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7Bdata%20%3D%20d%3B%20next%20%3D%20null%3B%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20void%20pairWiseSwap()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Traverse%20only%20till%20there%20are%20atleast%202%20nodes%20left%20*%2F%0A%20%20%20%20%20%20%20%20while%20(temp%20!%3D%20null%20%26%26%20temp.next%20!%3D%20null)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20Swap%20the%20data%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20k%20%3D%20temp.data%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp.data%20%3D%20temp.next.data%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp.next.data%20%3D%20k%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next.next%3B%0A%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%2F*%20Utility%20functions%20*%2F%0A%20%0A%20%20%20%20%2F*%20Inserts%20a%20new%20Node%20at%20front%20of%20the%20list.%20*%2F%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Put%20in%20the%20data*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%203.%20Make%20next%20of%20new%20Node%20as%20head%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Function%20to%20print%20linked%20list%20*%2F%0A%20%20%20%20void%20printList()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20while%20(temp%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20System.out.print(temp.data%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%3B%0A%20%20%20%20%20%20%20%20%7D%20%20%0A%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Created%20Linked%20List%201-%3E2-%3E3-%3E4-%3E5%20*%2F%0A%20%20%20%20%20%20%20%20llist.push(5)%3B%0A%20%20%20%20%20%20%20%20llist.push(4)%3B%0A%20%20%20%20%20%20%20%20llist.push(3)%3B%0A%20%20%20%20%20%20%20%20llist.push(2)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Linked%20List%20before%20calling%20pairWiseSwap()%20%22)%3B%0A%20%20%20%20%20%20%20%20llist.printList()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20llist.pairWiseSwap()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Linked%20List%20after%20calling%20pairWiseSwap()%20%22)%3B%0A%20%20%20%20%20%20%20%20llist.printList()%3B%0A%20%20%20%20%7D%0A%7D%20%0A%2F*%20This%20code%20is%20contributed%20by%20Rajat%20Mishra%20*%2F\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Linked List before calling pairWiseSwap() \r\n1 2 3 4 5 \r\nLinked List after calling pairWiseSwap() \r\n2 1 4 3 5<\/pre>\n<p>Time complexity: O(n)<\/p>\n<p><strong>METHOD 2 (Recursive)<\/strong><br \/>\nIf there are 2 or more than 2 nodes in Linked List then swap the first two nodes and recursively call for rest of the list.<\/p>\n<div>\u00a0<strong>Java\u00a0Programming:<\/strong><\/div>\n<div>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F*%20Recursive%20function%20to%20pairwise%20swap%20elements%20of%20a%20linked%20list%20*%2F%0Avoid%20pairWiseSwap(struct%20node%20*head)%0A%7B%0A%20%20%2F*%20There%20must%20be%20at-least%20two%20nodes%20in%20the%20list%20*%2F%0A%20%20if%20(head%20!%3D%20NULL%20%26%26%20head-%3Enext%20!%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20%20%20%2F*%20Swap%20the%20node\u2019s%20data%20with%20data%20of%20next%20node%20*%2F%0A%20%20%20%20%20%20swap(%26head-%3Edata%2C%20%26head-%3Enext-%3Edata)%3B%0A%20%20%20%20%0A%20%20%20%20%20%20%2F*%20Call%20pairWiseSwap()%20for%20rest%20of%20the%20list%20*%2F%0A%20%20%20%20%20%20pairWiseSwap(head-%3Enext-%3Enext)%3B%0A%20%20%7D%20%20%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<\/div>\n<div>Time complexity: O(n)<\/div>\n<div><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Java Algorithm &#8211; Pairwise swap elements of a given linked list &#8211; Linked List &#8211; Given a singly linked list, write a function to swap elements pairwise<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[80425,81794,80431,80424,81791,81792,80430,81793,80420,80421],"class_list":["post-27596","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-singly-linked-list","tag-how-to-swap-two-nodes-in-a-doubly-linked-list-java","tag-reverse-linked-list-in-pairs-java","tag-swap-adjacent-nodes-in-linked-list-java","tag-swap-alternate-nodes-linked-list","tag-swap-list-nodes-in-pairs","tag-swap-nodes-doubly-linked-list-c","tag-swap-nodes-in-linked-list","tag-swap-nodes-in-pairs-java","tag-swap-two-nodes-in-a-linked-list-java","tag-write-a-program-to-reverse-a-linked-list"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27596","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=27596"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27596\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}