143. Reorder List

Given a singly linked listL:L_0→_L_1→…→_Ln-1→L_n,
reorder it to:_L_0→_Ln→L_1→_Ln-1→L_2→_Ln-2→…

You maynotmodify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Thoughts:

practice for linking the nodes in linked list. Always draw a example out before writing the code

# 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: void Do not return anything, modify head in-place instead.
        """

        if not head or not head.next: return 

        slow = head
        fast = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next

        preM = slow
        preC = slow.next

        # reverse the second half of the node: 1->2->3->4->5->6: 1->2->3->6->5->4
        while preC.next:
            current = preC.next
            preC.next = current.next
            current.next = preM.next
            preM.next = current

        # insert right to left nodes one by one:
        p1 = head
        p2 = preM.next

        while p1 != preM:
            preM.next = p2.next
            p2.next =p1.next
            p1.next = p2
            p1 = p2.next
            p2 = preM.next