y12345678904 阅读(36) 评论(0)

题目

这里写图片描述

思路

1.拆分链表
2.后边链表就地逆置
3.merge

代码

# 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: return None
        preP1 = None
        p1 = head; p2 = head
        while p2 and p2.next:
            preP1 = p1
            p1 = p1.next
            p2 = p2.next.next
        if p1 != head:
            if preP1: preP1.next = None

            head2 = ListNode(0)
            while p1:
                tmp = p1.next
                p1.next = head2.next
                head2.next = p1
                p1 = tmp
            head2 = head2.next
            preHead = ListNode(0)
            node = preHead
            while head and head2:
                node.next = head
                head = head.next
                node = node.next

                node.next = head2
                head2 = head2.next
                node = node.next

            if head: 
                node.next = head
                node = node.next
            if head2:
                node.next = head2
                node = node.next