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
源代码文件在这里.
