原题
给定一个单链表L: L0→L1→…→Ln-1→Ln,
重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。
样例
给出链表 1->2->3->4->null，重新排列后为1->4->2->3->null。
解题思路
- 把题目分解成一个个小的任务
- 首先根据1->2->3->4，找中点，然后得到两个链表1->2和3->4
- 翻转第二个链表得到1->2和4->3
- 最后合并两个链表得到1->4->2->3
完整代码
# 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 head == None or head.next == None:
return
mid = self.findMiddle(head)
tail = self.reverse(mid.next)
mid.next = None
self.merge(head, tail)
def reverse(self, head):
newHead = None
while head != None:
temp = head.next
head.next = newHead
newHead = head
head = temp
return newHead
def merge(self, head1, head2):
index = 0
dummy = ListNode(0)
while head1 != None and head2 != None:
if index % 2 == 0:
dummy.next = head1
head1 = head1.next
else:
dummy.next = head2
head2 = head2.next
index += 1
dummy = dummy.next
if head1:
dummy.next = head1
if head2:
dummy.next = head2
def findMiddle(self, head):
slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
