FilesExpand file tree

 master

/

partition_list.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

46 lines (40 loc) · 1.39 KB

 master

/

partition_list.py

Top

File metadata and controls

• Code
• Blame

46 lines (40 loc) · 1.39 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#!/usr/bin/env python

'''

Leetcode: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

'''

from __future__ import division

import random

from LinkedList import Node

def part_list(head, val):

dummy = Node(None, next=head)

node = head

small = dummy # the end of "small part" of the link

large = dummy # the end of "large part" of the link

while node:

print head, 'small:', small.value, 'large:', large.value,

print 'current:', node, 'next:', node.next

next_node = node.next

if node.value >= val:

large = node

else:

# Change the connection

if small.next != node:

print 'move', node.value

node.next = small.next

small.next = node

large.next = next_node

# update the tail pointer to the small part

small = node

node = next_node

head = dummy.next

print head

return head

if __name__ == '__main__':

L = Node(1, Node(4, Node(3, Node(2, Node(5, Node(2))))))

part_list(L, 3)

L = Node(5, Node(2, Node(4, Node(4, Node(1, Node(2))))))

part_list(L, 4)