Switching the links in a linked list

  • Python
  • Thread starter FallenApple
  • Start date
  • #1
565
60

Main Question or Discussion Point

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.


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
 

Answers and Replies

  • #2
rcgldr
Homework Helper
8,697
528
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).
 
  • Like
Likes FallenApple
  • #3
85
12
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
 
  • Like
Likes FallenApple
  • #4
85
12
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
 

Related Threads on Switching the links in a linked list

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
20
Views
3K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
Top