LeetCode 143. Reorder List.jpg
LeetCode 143. Reorder List
Description
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify 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.
描述
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
思路
- 此题目主要分为三部分.
- 第一部分我们利用两个指针slow和fast，slow每次向后走一步，fast向后走两步，找到链表的中间位置.
- 第二部分我们将链表中间位置（不包括）后面的指针指向方向。及中间位置链表的next指向None,中间位置后面一个链表的next指向中间链表...以此类推，最后一个节点的next指向倒数第二个节点.
- 第三部分不断将最后一个节点放到前面部分.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-12 13:02:30
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-12 18:36:00
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reorderList(self, head):
"""
:type head: ListNode
:rtype: void Do not return anything, modify head in-place instead.
"""
# 如果head为空，或者只有一个节点，或者只有两个节点都不用进行交换
if not head or not head.next or not head.next.next:
return
# 第一部分：找到链表的中间值
middle, fast = head, head
while fast and fast.next:
middle = middle.next
fast = fast.next.next
# 第二部分将链表中间值后面的指针反转
Head, HeadNext = None, middle.next
middle.next = None
while HeadNext:
Head = HeadNext
HeadNext = HeadNext.next
Head.next = middle
middle = Head
# 第三部分交换指针
node, pre = head, Head
while pre.next:
pre = Head.next
Head.next = node.next
node.next = Head
node = Head.next
Head = pre
return
