问题陈述

Problem Statement:

Given a linked list(单链表) with integer data, arrange the elements in such a manner that all nodes with even numbers are placed after odd numbers. Do not create any new nodes and avoid using any other data structure. The relative order of even and odd elements must not change.

Example: * linked list = 1 2 3 4 5 6 * output = 1 3 5 2 4 6

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Node(object):
	def __init__(self, value):
		self.value = value
		self.next = None

def even_after_odd(head):
    first_even = None
    last_odd = None
    pre = head
    node = head
    flag_first_even = True
    while node != None:
        if node.value % 2 == 0 and flag_first_even:
            first_even = node
            flag_first_even = False
        if node.value % 2 != 0:
            last_odd = node
        if flag_first_even:
            pre = node 
        node = node.next
    node = first_even
    insert_pos_node = last_odd
    if first_even is None or last_odd is None:
        return head
    while node != last_odd:
        if node.value % 2 == 0:
            if node == head:
                head = pre.next
            else:
                pre.next = node.next
            even_node = node
            even_node.next = insert_pos_node.next
            insert_pos_node.next = even_node
            insert_pos_node = even_node
        else:
            pre = pre.next
        node = pre.next
    return head

测试用例： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# helper functions for testing purpose
def create_linked_list(arr):
    if len(arr)==0:
        return None
    head = Node(arr[0])
    tail = head
    for data in arr[1:]:
        tail.next = Node(data)
        tail = tail.next
    return head

def print_linked_list(head):
    while head:
        print(head.value, end=' ')
        head = head.next
    print()

def test_function(test_case):
    head = test_case[0]
    solution = test_case[1]
    
    node_tracker = dict({})
    node_tracker['nodes'] = list()
    temp = head
    while temp:
        node_tracker['nodes'].append(temp)
        temp = temp.next

    head = even_after_odd(head)    
    temp = head
    index = 0
    try:
        while temp:
            if temp.value != solution[index] or temp not in node_tracker['nodes']:
                print("Fail")
                return
            temp = temp.next
            index += 1
        print("Pass")            
    except Exception as e:
        print("Fail")

arr = [1, 2, 3, 4, 5, 6]
solution = [1, 3, 5, 2, 4, 6]

head = create_linked_list(arr)
test_case = [head, solution]
test_function(test_case)
print_linked_list(head)

arr = [1, 3, 5, 7]
solution = [1, 3, 5, 7]

head = create_linked_list(arr)
test_case = [head, solution]
test_function(test_case)
print_linked_list(head)    

arr = [2, 4, 6, 8]
solution = [2, 4, 6, 8]
head = create_linked_list(arr)
test_case = [head, solution]
test_function(test_case)
print_linked_list(head)