-
Notifications
You must be signed in to change notification settings - Fork 19
/
41_Split-Linked-List.py
55 lines (45 loc) · 1.27 KB
/
41_Split-Linked-List.py
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
#!/usr/bin/python
# coding=utf-8
'''
__author__ = 'sunp'
__date__ = '2019/1/28'
Given a linked list, write a function to split the list into two equal halves.
divide(1 -> 2 -> 3 -> 4) = 1 -> 2, 3 -> 4
divide(1 -> 2 -> 3 -> 4 -> 5) = 1 -> 2 -> 3, 4 -> 5
'''
from copy import deepcopy
class LinkNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
def divide(head):
fir, slow, fast = head, head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
sec = slow.next
slow.next = None
return fir, sec
if __name__ == '__main__':
test = LinkNode(1)
test.next = LinkNode(2)
test.next.next = LinkNode(3)
test.next.next.next = LinkNode(4)
test1 = deepcopy(test)
fir1, sec1 = divide(test1)
assert fir1.val == 1
assert fir1.next.val == 2
assert not fir1.next.next
assert sec1.val == 3
assert sec1.next.val == 4
assert not sec1.next.next
test2 = deepcopy(test)
test2.next.next.next.next = LinkNode(5)
fir2, sec2 = divide(test2)
assert fir2.val == 1
assert fir2.next.val == 2
assert fir2.next.next.val == 3
assert not fir2.next.next.next
assert sec2.val == 4
assert sec2.next.val == 5
assert not sec2.next.next