admin管理员组文章数量:1313162
I just started my college's data structures and algorithm's course and have some trouble with shifting nodes of even values to the back of my linked list. The function seems to work when there's only one even number present, but nothing ends up being printed out otherwise.
Below is my code (it's a little messy because I've been trying to debug it but I'm failing):
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def display(self):
current = self.head
while current:
print(current.data, end = " -> ")
current = current.next
print("None")
def move_even_items_to_back(self):
# Find the last node
last_node = self.head
while last_node.next:
last_node = last_node.next
current = self.head
prev = Node(None)
prev.next = self.head
while current:
if current.data % 2 == 0:
temp = current.next
# Add the node to the back
newNode = Node(current.data)
newNode.next = None
last_node.next = newNode
last_node = last_node.next
# Moving the previous node
if prev: # Not the head
prev.next = current.next
else: # Move head
self.head = current.next
# Removing current node
current.next = None
# Moving on
current = temp
else:
prev = current
current = current.next
node1 = Node(2)
node2 = Node(3)
node3 = Node(4)
node4 = Node(7)
node5 = Node(15)
node6 = Node(18)
ll = LinkedList()
ll.head = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
ll.display()
ll.move_even_items_to_back()
ll.display()
I've tried to use the current
variable and shift it directly to the back, and also to just create a new node with the same value and insert it to the back, and then removing the original node from the list, but both didn't work and nothing ended up being displayed.
I just started my college's data structures and algorithm's course and have some trouble with shifting nodes of even values to the back of my linked list. The function seems to work when there's only one even number present, but nothing ends up being printed out otherwise.
Below is my code (it's a little messy because I've been trying to debug it but I'm failing):
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def display(self):
current = self.head
while current:
print(current.data, end = " -> ")
current = current.next
print("None")
def move_even_items_to_back(self):
# Find the last node
last_node = self.head
while last_node.next:
last_node = last_node.next
current = self.head
prev = Node(None)
prev.next = self.head
while current:
if current.data % 2 == 0:
temp = current.next
# Add the node to the back
newNode = Node(current.data)
newNode.next = None
last_node.next = newNode
last_node = last_node.next
# Moving the previous node
if prev: # Not the head
prev.next = current.next
else: # Move head
self.head = current.next
# Removing current node
current.next = None
# Moving on
current = temp
else:
prev = current
current = current.next
node1 = Node(2)
node2 = Node(3)
node3 = Node(4)
node4 = Node(7)
node5 = Node(15)
node6 = Node(18)
ll = LinkedList()
ll.head = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
ll.display()
ll.move_even_items_to_back()
ll.display()
I've tried to use the current
variable and shift it directly to the back, and also to just create a new node with the same value and insert it to the back, and then removing the original node from the list, but both didn't work and nothing ended up being displayed.
1 Answer
Reset to default 1When your list has 2 or more even numbers, then you'll iterate into the nodes that you have already appended at the end of the linked list and move them again to the back of the list, and so your code never reaches the end of the list.
Unrelated to this issue, but it seems likely that you're not supposed to create new nodes to be appended, but should really rewire the nodes you already have. So except for creating temporary sentinel node(s), you should not have any other call to Node()
in the function move_even_items_to_back
.
An easier approach to this challenge is to maintain an "odd" and "even" linked list, each time appending a node to one of these two. When all nodes have been so distributed, you can link the tail of the odd list to the head of the even list.
Here is a suggested implementation:
def move_even_items_to_back(self):
odd_sentinel = Node(None)
odd_tail = odd_sentinel
even_sentinel = Node(None)
even_tail = even_sentinel
# Distribute the nodes in two linked lists
node = self.head
while node:
if node.data % 2: # odd?
odd_tail.next = node
odd_tail = node
else:
even_tail.next = node
even_tail = node
node = node.next
# Properly terminate the even list
even_tail.next = None
# Append the even list at the end of the odd one
odd_tail.next = even_sentinel.next
# Register the first node of that merged list
self.head = odd_sentinel.next
本文标签: pythonShifting even numbers to the back of a linked listStack Overflow
版权声明:本文标题:python - Shifting even numbers to the back of a linked list - Stack Overflow 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/web/1741911631a2404478.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
move_to_back()
on the even ones. – Barmar Commented Jan 31 at 16:29