First, partition the lists into 2 using the fast and slow pointer method.
Then, reverse the second list
Then, just need to stitch them together. When partitioning, need to pay close attention to how to cut it if the fast pointer is None or not, see the partition_lists() subroutine.
class Solution(object): def partition_lists(self, head): slow = head fast = head prev = None while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next list1 = head list2 = None if not fast: list2 = slow prev.next = None else: list2 = slow.next slow.next = None return list1, list2 def reverse_list(self, head): prev = None curr = head while curr: temp = curr.next curr.next = prev prev = curr curr = temp head = prev return head def reorderList(self, head): """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """ if not head: return list1, list2 = self.partition_lists(head) list2 = self.reverse_list(list2) while list1 and list2: temp = list2.next list2.next = None temp2 = list1.next list1.next = list2 list2.next = temp2 list2 = temp list1 = temp2