python - Shifting even numbers to the back of a linked list - Stack Overflow

admin管理员组

文章数量:1313378

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.

• python
• data-structures
• linked-list

Share Improve this question Follow edited Jan 31 at 17:16 trincot 351k3636 gold badges272272 silver badges325325 bronze badges asked Jan 31 at 15:07 irusuugenirusuugen 111 bronze badge 2

• 2 Do you want to create a new node when moving or do you want to set last.next to point to the node you want to move and then update last? Note as well, once you move a second even node to the end, you have two even end nodes and you perpetually move one after the other. – JonSG Commented Jan 31 at 15:13
• I recommend you split this into two functions. Write a method that moves a node to the back. Then write another method that iterates over the list, calling move_to_back() on the even ones. – Barmar Commented Jan 31 at 16:29

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 1

When 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