[LeetCode] 143.並べ替えリストの問題解決レポート（Python）

143 Reorder List Problem Solving Report

ラベル（スペース区切り）：LeetCode

著者：Xue MingZhuネガティブ
id：fuxuemingzhu
個人ブログ： http://fuxuemingzhu.me/

---

タイトルアドレス： https://leetcode.com/problems/reorder-list/description/

タイトル説明：

単一リンクリストLが与えられた場合：L0→L1→…→Ln-1→Ln、
次のように並べ替えます：L0→Ln→L1→Ln-1→L2→Ln-2→…

リストのノードの値を変更することはできません。変更できるのはノード自体のみです。

例1：

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

例2：

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

件名

リンクリストの前半は正順、後半は逆順で、1つずつ接続されています。

問題解決方法

タイトルの通り、3つのステップが必要です。実際、この質問は非常に巧妙で、リンクリストの調査で詳しく説明されています。 3つの質問と言えます。

コードは少し長く、3つのステップで書かれています。この問題では、新しいノードを返すことができないため、問題が大きくなります。

参照： [leetcode]並べ替えリスト@Python

# 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 and head.next and head.next.next: #find mid fast, slow = head, head while fast.next and fast.next.next: fast = fast.next.next slow = slow.next head1 = head head2 = slow.next slow.next = None # reverse linked list head2 dummy = ListNode(0) dummy.next = head2 p = head2.next head2.next = None while p: temp = p p = p.next temp.next = dummy.next dummy.next = temp head2 = dummy.next # merge two linked list head1 and head2 p1 = head1 p2 = head2 while p2: temp1 = p1.next temp2 = p2.next p1.next = p2 p2.next = temp1 p1 = temp1 p2 = temp2

日付

2018年6月25日---新しい週、物事を心配するのをやめなさい。