aboutsummaryrefslogtreecommitdiff
path: root/reorder_list.py
diff options
context:
space:
mode:
Diffstat (limited to 'reorder_list.py')
-rw-r--r--reorder_list.py42
1 files changed, 42 insertions, 0 deletions
diff --git a/reorder_list.py b/reorder_list.py
new file mode 100644
index 0000000..c25a277
--- /dev/null
+++ b/reorder_list.py
@@ -0,0 +1,42 @@
+# 143. Reorder List
+
+"""
+given the head of a singly linked list. the list can be represented as 'l0 ->
+l1 -> ... -> Ln'. reorder the list to be of the following form: 'l0 -> ln ->
+ln-1 -> ln-2'. you may not modify the values in the list's nodes. only nodes
+themselves may be changed.
+"""
+
+
+# Definition for singly-linked list.
+class ListNode(object):
+ def __init__(self, val=0, next=None):
+ self.val = val
+ self.next = next
+
+
+class Solution(object):
+ def reorderList(self, head):
+ """
+ :type head: ListNode
+ :rtype: None Do not return anything, modify head in-place instead.
+ """
+ if not head:
+ return []
+ slow, fast = head, head
+ while fast.next and fast.next.next:
+ slow = slow.next
+ fast = fast.next.next
+ prev, curr = None, slow.next
+ while curr:
+ tmp = curr.next
+ curr.next = prev
+ prev = curr
+ curr = tmp
+ slow.next = None
+ head1, head2 = head, prev
+ while head2:
+ tmp = head1.next
+ head1.next = head2
+ head1 = head2
+ head2 = tmp