Swapping head and tail of a single linked list

Question

I have been stuck on this for half of a day. Could I get some tips or pointers on how to swap just the head and tail of a linked list (not reverse the entire list) without copying their data?

class myNode:

    def __init__(data, next):
         self.data = data
         self.next = next


class MyLinkedList:

    def __init__(self):
         self.head = None
         self.tail = None

If I could see the code and have an explanation to it, that would be awesome!

edit:

Basically, my initial way of solving this problem is.

1. Literate through the list to find the tail ( by stopping the while loop when the node.next is None, meaning I have reached the end)

and then linking the tail to the head.next

2. Literate through the list to find the 2nd last node of the list and linking that to the head.

3. Linking the original head to null as now the head should be swapped to the tail.

Answer 1

There are a few edge cases which are best handled separately to keep the code simple. They are lists of size zero, one and two.

For the first two of those, the list will not change at all. For size two, only the head and tail will change, no internal nodes will (because there are no internal nodes).

In that case, the list on the left becomes the one on the right with (| indicates a null pointer and h/t are the head and tail pointers):

h    t               h    t
A -> B -> |          B -> A -> |

with (this is pseudo-code rather than Python, .n specifies the next pointer):

                     h=A  t=B  A.n=B  B.n=|
tail.next = head     h=A  t=B  A.n=B  B.n=A
head.next = null     h=A  t=B  A.n=|  B.n=A
swap head, tail      h=B  t=A  A.n=|  B.n=A

For all other cases (three or more nodes), the penultimate node must have its pointer changed to point to the new tail. The two-node case above can be easier because it knows the head is the penultimate. The following diagram shows the case for size four (I have marked the penultimate node with p):

h         p    t          h         p    t
A -> B -> C -> D -> |     D -> B -> C -> A -> |

This can be achieved with the following operations:

                          h=A  t=D  p=C A.n=B  B.n=C C.n=D  D.n=|
tail.next = head.next     h=A  t=D  p=C A.n=B  B.n=C C.n=D  D.n=B
head.next = None          h=A  t=D  p=C A.n=|  B.n=C C.n=D  D.n=B
penu.next = head          h=A  t=D  p=C A.n=|  B.n=C C.n=A  D.n=B
swap head, tail           h=D  t=A  p=C A.n=|  B.n=C C.n=A  D.n=B

So, in terms of putting that into Python, the following program contains both the methods and a test harness so you can see it in operation:

class MyNode:
    def __init__(self, data, next = None):
         self.data = data
         self.next = next

class MyList:
    def __init__(self):
         self.head = None
         self.tail = None

    def push_back(self, data):
        if self.tail is None:
            self.head = MyNode(data)
            self.tail = self.head
        else:
            self.tail.next = MyNode(data)
            self.tail = self.tail.next

    def dump(self, desc):
        print(desc, end=' ')
        node = self.head
        while node is not None:
            print(node.data, end=' -> ')
            node = node.next
        print('|')

    def swap(self):
        # For empty and size 1, no change.

        if self.head is None: return
        if self.head.next is None: return

        # For size 2, easy swap.

        if self.head.next.next is None:
            self.tail.next = self.head
            self.head.next = None
            self.head, self.tail = self.tail, self.head
            return

        # For size 3+, little more complex, need the
        # penultimate node as well as head and tail.

        penu = self.head
        while penu.next != self.tail:
            penu = penu.next

        self.tail.next = self.head.next
        self.head.next = None
        penu.next = self.head
        self.head, self.tail = self.tail, self.head

First the node class, modified as per Hans' suggestion to default the next pointer. Then the list class itself, with initialisation as per your original question.

It also has a push_back method since a list is of little use if you can't put anything in it, and a dump method so we can see what the list looks like after each operation.

The only other part of that class is the swap method, the logic which has been covered in the earlier part of this answer.

And, of course, what self-respecting class could exist without some sort of test code. The following will test lists of varying sizes so that you can see the swap operation works as expected:

x = MyList()

# Do various sizes.

for i in range(6):
    # Add an element except for first time (so we check empty list).

    if i > 0:
        x.push_back(i)

    # Show before and after figures, making sure we restore
    # list to original state.

    x.dump('Size = %d, before:'%(i))
    x.swap()
    x.dump('Size = %d, after :'%(i))
    x.swap()
    print()

Running this code results in:

Size = 0, before: |
Size = 0, after : |

Size = 1, before: 1 -> |
Size = 1, after : 1 -> |

Size = 2, before: 1 -> 2 -> |
Size = 2, after : 2 -> 1 -> |

Size = 3, before: 1 -> 2 -> 3 -> |
Size = 3, after : 3 -> 2 -> 1 -> |

Size = 4, before: 1 -> 2 -> 3 -> 4 -> |
Size = 4, after : 4 -> 2 -> 3 -> 1 -> |

Size = 5, before: 1 -> 2 -> 3 -> 4 -> 5 -> |
Size = 5, after : 5 -> 2 -> 3 -> 4 -> 1 -> |

---

Once you're satisfied that this works, you might want to look into making penu (the penultimate node pointer) into a member just like head and tail, and set it to None if the size is two or less. That way, you won't have to search every time you want to swap the nodes. It should be relatively easy to update this whenever calling push_back (or any other method which changes the size of list).

Answer 2

After reviewing the code @Waffle linked, the following seem to be the important classes. The first represents nodes in a linked list, and the second is a container class for nodes allowing easy representations of empty lists. The goal is to implement LinkedList.swap_front_back() in a way that mutates the represented list in-place.

class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def swap_front_back(self):
        """TODO: Magic happens here"""

Since Python has an implicit return of None, using returns as a way of breaking out a function even if it supposedly "doesn't return anything" is a safe exit strategy. Hence, the following couple lines gets rid of the smallest edge cases:

if self.size < 2:
    return

The strategy I proposed for swapping the list in-place involved a second-to-last element, and all kinds of bad things happen if that happens to be the first element. In other words, we unfortunately have to deal with the case of a linked list of size 2 as a special case (for this implementation).

if self.size == 2:
    self.head, self.tail = self.tail, self.head
    self.head.next = self.tail
    self.tail.next = None
    return

In the general case, we need to change where the second-to-last element of the linked list points. If this doesn't happen the linked list becomes a cycle, and all kinds of bad things happen in algorithms which expect the list to end.

current = self.head
while current.next.next is not None:
    current = current.next

Once the second-to-last element is found, we can go through with the actual pointer manipulations.

current.next.next = self.head.next
# Now the former last element points to the second element
# A->B->C->D->B

current.next = self.head
# Now the second-to-last element points to the previous head
# A->B->C->A   D->B

self.head.next = None
# We don't want circles, so we eliminate A being first and last
# D->B->C->A

self.head, self.tail = self.tail, self.head
# Even after the internal manipulations are done, the
# LinkedList needs to be updated to reference the appropriate
# locations.

Putting it all together, we can create the desired method:

def swap_front_back(self):
    if self.size < 2:
        return

    if self.size == 2:
        self.head, self.tail = self.tail, self.head
        self.head.next = self.tail
        self.tail.next = None
        return

    current = self.head
    while current.next.next is not None:
        current = current.next

    self.tail.next = self.head.next
    current.next = self.head
    self.head.next = None
    self.head, self.tail= self.tail, self.head

This returns early if the LinkedList is so small that no swaps need happen, it deals with a transposition as a special case, and otherwise it first finds the second-to-last node and then uses that to adjust the requisite pointers.

Answer 3

Generally, swaps rely on a third variable to store one of the values to be reversed. For instance, given list [3, 4, 1, 6, 5], swapping the first and the last can be accomplished like so:

l = [3, 4, 1, 6, 5]
_temp = l[0] #first value
l[0] = l[-1]
l[-1] = _temp
#[5, 4, 1, 6, 3]

The implementation below utilizes a default parameter that will store the reference to the first node in the list. Once the end of the list has been reached, the simple swap operation, similar to the swap above, will take place:

class LinkedList:
  def __init__(self, head=None):
    self.head = head
    self._next = None
  def insert_node(self, val):
    if self.head is None:
      self.head = val
    else:
      getattr(self._next, 'insert_node', lambda x:setattr(self, '_next', LinkedList(x)))(val)
  def swap(self, first = None, count = 0):
    if not self._next and self.head is not None:
       _head = getattr(self, 'head')
       if first:
         self.head = getattr(first, 'head')
         setattr(first, 'head', _head)
    else:
       if self.head:
         self._next.swap(first = self if not count else first, count = 1)
  @classmethod
  def load_list(cls, length = 5):
    _l = cls()
    import random
    for _ in range(length):
      _l.insert_node(random.randint(1, 100))
    return _l
  def flatten(self):
    if self.head is not None:
      return [self.head, *getattr(self._next, 'flatten', lambda :'')()]
    return ''
  def __repr__(self):
    return ', '.join(map(str, self.flatten()))

This simple recursion will work for lists of any size:

for i in range(10):
   l = LinkedList.load_list(length = i)
   _s = repr(l)
   l.swap()
   print(f'{_s} -> {repr(l)}')

Output:

 -> 
14 -> 14
80, 57 -> 57, 80
83, 44, 80 -> 80, 44, 83
94, 10, 42, 81 -> 81, 10, 42, 94
25, 26, 32, 31, 55 -> 55, 26, 32, 31, 25
8, 25, 25, 84, 83, 49 -> 49, 25, 25, 84, 83, 8
19, 95, 3, 33, 4, 56, 33 -> 33, 95, 3, 33, 4, 56, 19
97, 92, 37, 100, 27, 24, 33, 17 -> 17, 92, 37, 100, 27, 24, 33, 97
72, 24, 56, 18, 9, 64, 82, 85, 97 -> 97, 24, 56, 18, 9, 64, 82, 85, 72

Answer 4

Initially say you have A -> B -> C -> D -> None Head: A Tail: D

You want D -> B -> C -> A -> None Head: D, Tail: A

var next = self.head.next
var temp = self.head
self.head = self.tail
self.tail = temp
self.head.next = next
self.tail.next = None