Reverse in Pair
by Isai Damier, Android Engineer @ Google
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #======================================================================= # Author: Isai Damier # Title: Singly Linked List # Project: geekviewpoint # Package: datastructure # # Description: A LinkedList is a data structure that allows access # to a collection of data using pointers/references. While an # array can also be defined as above, LinkedLists and arrays differ # in how they are stored in memory and in the operations they # allow. Unlike an array that must be stored in a block of memory, # the nodes of a LinkedList can be stored anywhere because each # node has a reference to the node that succeeds it. Because the # nodes are stored so loosely, inserting nodes into a LinkedList # is easy; whereas in an array, all the succeeding elements must # be shifted. Of course, insertion also means changing the size of # the array, which means creating the entire array anew. # # Perhaps the greatest beauty of LinkedList is that it allows # accessing an entire sequence of nodes using only one variable: # a reference to the first node in the sequence. # # Countless operations can be performed on LinkedLists. Following # are a few, ranging from the common to the very interesting. #======================================================================= #===================================================================== # Time Complexity of Solution: # O(n). # # Description: Reverse each pair of nodes, such that abcdefg # becomes badcfeg. #===================================================================== import collections class SinglyLinkedList( object ): def __init__( self ): self .head , self .tail = None , None def reverseInPairs( self ) : t = self .head while None ! = t and None ! = t. next : self .swapData( t, t. next ) t = t. next . next def swapData( self , a, b ): tmp = a.data a.data = b.data b.data = tmp class Node( object ): def __init__( self , data, next = None ): self .data = data self . next = next |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | import unittest from algorithms.SinglyLinkedList import SinglyLinkedList import random class Test( unittest.TestCase ): #===================================================================== # Test of reverseInPairs method, of class SinglyLinkedList. #===================================================================== def testReverseInPairs( self ): tape = [ 9 , 4 , 5 , 2 , 1 , 12 , 6 , 7 , 4 , 8 , 3 , 0 , 16 , 19 , 11 ] linkedList = SinglyLinkedList() for i in range ( len ( tape ) ): linkedList.addToTail( tape[i] ) self .assertEquals( tape, linkedList.toArray() ) linkedList.reverseInPairs() exp = [ 4 , 9 , 2 , 5 , 12 , 1 , 7 , 6 , 8 , 4 , 0 , 3 , 19 , 16 , 11 ] self .assertEquals( exp, linkedList.toArray() ) |