{"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":"

Given a linked list<\/a> and two keys in it, 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><\/p>\n

It may be assumed that all keys in linked list are distinct.<\/p>\n

Examples:<\/strong><\/span><\/h3>\n
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
This may look a simple problem, but is interesting question as it has following cases to be handled.
\n1) x and y may or may not be adjacent.
\n2) Either x or y may be a head node.
\n3) Either x or y may be last node.
\n4) x and\/or y may not be present in linked list.<\/p>\n[ad type=”banner”]\n
How to write a clean working code that handles all of the above possibilities.<\/p>\n
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 python<\/a> implementation of this approach.<\/p>\n
Python Programming:<\/strong><\/span><\/h3>\n
 
 <\/div> 
# Python program to swap two given nodes of a linked listclass LinkedList(object):    def __init__(self):        self.head = None     # head of list    class Node(object):        def __init__(self, d):            self.data = d            self.next = None     # Function to swap Nodes x and y in linked list by    # changing links    def swapNodes(self, x, y):         # Nothing to do if x and y are same        if x == y:            return         # Search for x (keep track of prevX and CurrX)        prevX = None        currX = self.head        while currX != None and currX.data != x:            prevX = currX            currX = currX.next         # Search for y (keep track of prevY and currY)        prevY = None        currY = self.head        while currY != None and currY.data != y:            prevY = currY            currY = currY.next         # If either x or y is not present, nothing to do        if currX == None or currY == None:            return        # If x is not head of linked list        if prevX != None:            prevX.next = currY        else: #make y the new head            self.head = currY         # If y is not head of linked list        if prevY != None:            prevY.next = currX        else: # make x the new head            self.head = currX         # Swap next pointers        temp = currX.next        currX.next = currY.next        currY.next = temp     # Function to add Node at beginning of list.    def push(self, new_data):         # 1. alloc the Node and put the data        new_Node = self.Node(new_data)         # 2. Make next of new Node as head        new_Node.next = self.head         # 3. Move the head to point to new Node        self.head = new_Node     # This function prints contents of linked list starting    # from the given Node    def printList(self):        tNode = self.head        while tNode != None:            print tNode.data,            tNode = tNode.next # Driver program to test above functionllist = LinkedList() # The constructed linked list is:# 1->2->3->4->5->6->7llist.push(7)llist.push(6)llist.push(5)llist.push(4)llist.push(3)llist.push(2)llist.push(1)print "Linked list before calling swapNodes() "llist.printList()llist.swapNodes(4, 3)print "\\nLinked list after calling swapNodes() "llist.printList() # This code is contributed by BHAVYA JAIN<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
 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
Optimizations:<\/strong> <\/span>The above code can be optimized to search x and y in single traversal. Two loops<\/a> are used to keep program simple.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python Algorithm – Swap nodes in a linked list without swapping data – Linked List – 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}]}}