Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python Switching the links in a linked list

  1. Jan 30, 2017 #1
    So I have a linked list a->b->c->d

    and I want to make another list

    b->a->d->c

    in a systematic way by interchanging pointers. But for some reason it isn't working. All I did was move the link between b and c into b to a. Then the link from a to b, changed to a to d. Then the one connecting c to d is reversed. I'm not sure what went wrong.


    Code (Python):


    class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None
           
           
           
    A=['a','b','c','d']
    head=ListNode(A[0])
    #filling the linked list with abcd
    temp=head
    for i in A[1:]:
      temp.next=ListNode(i)
      temp=temp.next
     
     
    point=head
    print("the current linked list")

    while(point):
      print(point.val)
      point=point.next

    print("   ")

    #attempting to alter the list
    Temp1=head.next.next  
    head.next.next=head    # moving the link between b-c to a
    Temp2=head.next
    head.next=head.next.next.next  #moving the link between a-b to d
    head.next.next.next=Temp1    #moving the link between d and c
    head=Temp2

    #print(head)
    print("the new linkedlist")
    point=head

    while(point):
      print(point.val)
      point=point.next





     

    The output is

    the current linked list
    a
    b
    c
    d

    the new linkedlist
    b
    a
    c
    d
     
  2. jcsd
  3. Jan 30, 2017 #2

    rcgldr

    User Avatar
    Homework Helper

    You have to avoid using any links that you've changed, either with careful ordering of operations and/or using temp pointers to avoid conflicts.

    For example, if swapping two nodes in a linked list, if the nodes are adjacent, the next pointers are effectively rotated, but if the nodes are not adjacent, then two pairs of next pointers are swapped. This can be handled with common code by first swapping the external pointers to the two nodes, followed by swapping the nodes internal next pointers.

    Given a list a->b->c->d->e->f, to swap b and e, swap(a->next, d->next), swap(b->next, e->next). To swap c and d, swap(b->next, c->next), swap(c->next, d->next).
     
  4. Feb 8, 2017 #3
    Implement as a doubly linked list. In that data structure any given node knows who's it is attached to. Be very careful with the pointer manipulation or orphaned nodes (and thus memory leaks) will occur
     
  5. Feb 8, 2017 #4
    Also make sure to test the link pointers for null so that the node is valid. Usually the "next" pointer is null to indicate there are no further nodes
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Switching the links in a linked list
  1. Linked List (Replies: 9)

  2. Linked list (Replies: 12)

  3. Java linked list (Replies: 1)

  4. Linked list Fortran (Replies: 20)

Loading...