{"id":26937,"date":"2017-12-28T21:45:03","date_gmt":"2017-12-28T16:15:03","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26937"},"modified":"2018-10-30T17:02:42","modified_gmt":"2018-10-30T11:32:42","slug":"python-algorithm-swap-nodes-linked-list-without-swapping-data","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-swap-nodes-linked-list-without-swapping-data\/","title":{"rendered":"Swap nodes in a linked list without swapping data"},"content":{"rendered":"<p>Given a <a href=\"https:\/\/www.wikitechy.com\/technology\/python-algorithm-find-length-linked-list-iterative-recursive\/\" target=\"_blank\" rel=\"noopener\">linked list<\/a> and two keys in it, <a href=\"https:\/\/www.wikitechy.com\/technology\/python-algorithm-pairwise-swap-elements-given-linked-list\/\" target=\"_blank\" rel=\"noopener\">swap nodes<\/a> for two given keys. Nodes should be swapped by changing links. Swapping data of nodes may be expensive in many situations when data contains many fields.<span id=\"more-134695\"><\/span><\/p>\n<p>It may be assumed that all keys in linked list are distinct.<\/p>\n<h3 id=\"examples\"><span style=\"color: #000080;\"><strong>Examples:<\/strong><\/span><\/h3>\n<pre>Input:  10->15->12->13->20->14,  x = 12, y = 20\r\nOutput: 10->15->20->13->12->14\r\n\r\nInput:  10->15->12->13->20->14,  x = 10, y = 20\r\nOutput: 20->15->12->13->10->14\r\n\r\nInput:  10->15->12->13->20->14,  x = 12, y = 13\r\nOutput: 10->15->13->12->20->14<\/pre>\n<p>This may look a simple problem, but is interesting question as it has following cases to be handled.<br \/>\n1) x and y may or may not be adjacent.<br \/>\n2) Either x or y may be a head node.<br \/>\n3) Either x or y may be last node.<br \/>\n4) x and\/or y may not be present in linked list.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>How to write a clean working code that handles all of the above possibilities.<\/p>\n<p>The idea it to first search x and y in given linked list. If any of them is not present, then return. While searching for x and y, keep track of current and previous pointers. First change next of previous pointers, then change next of current pointers. Following <a href=\"https:\/\/www.wikitechy.com\/tutorials\/python\/python-program-to-reverse-a-number\" target=\"_blank\" rel=\"noopener\">python<\/a> implementation of this approach.<\/p>\n<h3 id=\"python-programming\"><span style=\"color: #333399;\"><strong>Python Programming:<\/strong><\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20swap%20two%20given%20nodes%20of%20a%20linked%20list%0Aclass%20LinkedList(object)%3A%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%20%20%20%23%20head%20of%20list%0A%20%20%20%20class%20Node(object)%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20d)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.data%20%3D%20d%0A%20%20%20%20%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%0A%20%20%20%20%23%20Function%20to%20swap%20Nodes%20x%20and%20y%20in%20linked%20list%20by%0A%20%20%20%20%23%20changing%20links%0A%20%20%20%20def%20swapNodes(self%2C%20x%2C%20y)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20Nothing%20to%20do%20if%20x%20and%20y%20are%20same%0A%20%20%20%20%20%20%20%20if%20x%20%3D%3D%20y%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%0A%20%20%20%20%20%20%20%20%23%20Search%20for%20x%20(keep%20track%20of%20prevX%20and%20CurrX)%0A%20%20%20%20%20%20%20%20prevX%20%3D%20None%0A%20%20%20%20%20%20%20%20currX%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while%20currX%20!%3D%20None%20and%20currX.data%20!%3D%20x%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prevX%20%3D%20currX%0A%20%20%20%20%20%20%20%20%20%20%20%20currX%20%3D%20currX.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20Search%20for%20y%20(keep%20track%20of%20prevY%20and%20currY)%0A%20%20%20%20%20%20%20%20prevY%20%3D%20None%0A%20%20%20%20%20%20%20%20currY%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while%20currY%20!%3D%20None%20and%20currY.data%20!%3D%20y%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prevY%20%3D%20currY%0A%20%20%20%20%20%20%20%20%20%20%20%20currY%20%3D%20currY.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20either%20x%20or%20y%20is%20not%20present%2C%20nothing%20to%20do%0A%20%20%20%20%20%20%20%20if%20currX%20%3D%3D%20None%20or%20currY%20%3D%3D%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%23%20If%20x%20is%20not%20head%20of%20linked%20list%0A%20%20%20%20%20%20%20%20if%20prevX%20!%3D%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prevX.next%20%3D%20currY%0A%20%20%20%20%20%20%20%20else%3A%20%23make%20y%20the%20new%20head%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20currY%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20y%20is%20not%20head%20of%20linked%20list%0A%20%20%20%20%20%20%20%20if%20prevY%20!%3D%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prevY.next%20%3D%20currX%0A%20%20%20%20%20%20%20%20else%3A%20%23%20make%20x%20the%20new%20head%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20currX%0A%20%0A%20%20%20%20%20%20%20%20%23%20Swap%20next%20pointers%0A%20%20%20%20%20%20%20%20temp%20%3D%20currX.next%0A%20%20%20%20%20%20%20%20currX.next%20%3D%20currY.next%0A%20%20%20%20%20%20%20%20currY.next%20%3D%20temp%0A%20%0A%20%20%20%20%23%20Function%20to%20add%20Node%20at%20beginning%20of%20list.%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%201.%20alloc%20the%20Node%20and%20put%20the%20data%0A%20%20%20%20%20%20%20%20new_Node%20%3D%20self.Node(new_data)%0A%20%0A%20%20%20%20%20%20%20%20%23%202.%20Make%20next%20of%20new%20Node%20as%20head%0A%20%20%20%20%20%20%20%20new_Node.next%20%3D%20self.head%0A%20%0A%20%20%20%20%20%20%20%20%23%203.%20Move%20the%20head%20to%20point%20to%20new%20Node%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_Node%0A%20%0A%20%20%20%20%23%20This%20function%20prints%20contents%20of%20linked%20list%20starting%0A%20%20%20%20%23%20from%20the%20given%20Node%0A%20%20%20%20def%20printList(self)%3A%0A%20%20%20%20%20%20%20%20tNode%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while%20tNode%20!%3D%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20tNode.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tNode%20%3D%20tNode.next%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Allist%20%3D%20LinkedList()%0A%20%0A%23%20The%20constructed%20linked%20list%20is%3A%0A%23%201-%3E2-%3E3-%3E4-%3E5-%3E6-%3E7%0Allist.push(7)%0Allist.push(6)%0Allist.push(5)%0Allist.push(4)%0Allist.push(3)%0Allist.push(2)%0Allist.push(1)%0Aprint%20%22Linked%20list%20before%20calling%20swapNodes()%20%22%0Allist.printList()%0Allist.swapNodes(4%2C%203)%0Aprint%20%22%5CnLinked%20list%20after%20calling%20swapNodes()%20%22%0Allist.printList()%0A%20%0A%23%20This%20code%20is%20contributed%20by%20BHAVYA%20JAIN\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre> Linked list before calling swapNodes() \r\n  1 2 3 4 5 6 7\r\n Linked list after calling swapNodes() \r\n  1 2 4 3 5 6 7<\/pre>\n<p><span style=\"color: #0000ff;\"><strong>Optimizations:<\/strong> <\/span>The above code can be optimized to search x and y in single traversal. Two <a href=\"https:\/\/www.wikitechy.com\/tutorials\/python\/python-loop\" target=\"_blank\" rel=\"noopener\">loops<\/a> are used to keep program simple.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Python Algorithm &#8211; Swap nodes in a linked list without swapping data &#8211; Linked List &#8211; Given a linked list and two keys in it, swap nodes for two given keys<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,4148,79478],"tags":[80425,80422,80431,80424,80427,80423,80428,80430,80426,80420,80429,80421],"class_list":["post-26937","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-python","category-singly-linked-list","tag-how-to-swap-two-nodes-in-a-doubly-linked-list-java","tag-swap-adjacent-nodes-in-linked-list","tag-swap-adjacent-nodes-in-linked-list-java","tag-swap-alternate-nodes-linked-list","tag-swap-kth-node-from-beginning-with-kth-node-from-end-in-a-linked-list","tag-swap-nodes-doubly-linked-list","tag-swap-nodes-in-doubly-linked-list-java","tag-swap-nodes-in-linked-list","tag-swap-two-adjacent-elements-linked-list-java","tag-swap-two-nodes-in-a-linked-list-java","tag-swapping-two-nodes-in-a-doubly-linked-list-c","tag-write-a-program-to-reverse-a-linked-list"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26937","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=26937"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26937\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26937"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26937"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26937"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}