| 16 | self.next = None |
| 17 | |
| 18 | class Solution(object): |
| 19 | def reorderList(self, head): |
| 20 | if not head or not head.next: |
| 21 | return |
| 22 | ahead, behind = self.split(head) |
| 23 | behind = self.reverse(behind) |
| 24 | head = self.reConnect(ahead, behind) |
| 25 | # split the linkedlist in middle |
| 26 | def split(self, head): |
| 27 | fast = head |
| 28 | slow = head |
| 29 | while fast and fast.next: |
| 30 | slow = slow.next |
| 31 | fast = fast.next |
| 32 | fast = fast.next |
| 33 | middle = slow.next |
| 34 | slow.next = None |
| 35 | return head, middle |
| 36 | # reverse the behind half linkedlist |
| 37 | def reverse(self, head): |
| 38 | reHead = None |
| 39 | curNode = head |
| 40 | while curNode: |
| 41 | nextNode = curNode.next |
| 42 | curNode.next = reHead |
| 43 | reHead = curNode |
| 44 | curNode = nextNode |
| 45 | return reHead |
| 46 | # merge the two linkedlist to one |
| 47 | def reConnect(self, first, second): |
| 48 | head = first |
| 49 | tail = first |
| 50 | first = first.next |
| 51 | while second: |
| 52 | tail.next = second |
| 53 | tail = tail.next |
| 54 | second = second.next |
| 55 | if first: |
| 56 | first, second = second, first |
| 57 | return head |
nothing calls this directly
no outgoing calls
no test coverage detected