-
Notifications
You must be signed in to change notification settings - Fork 0
/
143.py
55 lines (48 loc) · 1.37 KB
/
143.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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return head
leng, p = 0, head
while p:
p = p.next
leng += 1
half1 = (leng-1) / 2 + (leng-1) % 2
p, cnt, half2 = head.next, 0, None
while p:
cnt += 1
if cnt == half1:
half2 = p.next
p.next = None # 这里是要点,不然环状
break
p = p.next
half2 = self.reverseList(half2)
pre, q = head, half2
while q != None:
curp = pre
pre = pre.next
curq = q
q = q.next
curq.next = curp.next
curp.next = curq
def reverseList(self, head):
if not head:
return head
tmp = ListNode(-1)
tmp.next = head
p = head.next
tmp.next.next = None
while p:
cur = p
p = p.next
cur.next = tmp.next
tmp.next = cur
return tmp.next