LeetCode -- Reorder List
2735 ワード
タイトル説明:Given a singly linked list L:L 0→L 1→...→Ln-1→Ln、reorder it to:L 0→Ln→L 1→Ln-1→L 2→Ln-2→…You must do this in-place without altering the nodes'values.For example,Given {1,2,3,4}, reorder it to {1,4,2,3}.この問題はチェーンテーブルの中で特徴的な問題です.チェーンテーブル1−>2−>3−>4−>5−>6の場合、i番目のノードは最後からi番目のノードを指し、最後からi番目のノードはi+1番目のノードを指す.解法1:前後の2つのポインタpとqを使用する.具体的な実装手順については、ここでは説明しないでください.時間的な複雑さがO(N^2)であるため,効率が不十分でタイムアウトする.OJのテストデータに合格できません.実装コード:
解法二:本実装は接続を参照した.http://www.acmerblog.com/reorder-list-leetcode-6088.html1.slowとfastポインタを使用してチェーンテーブルを2つの部分に分け、part 1とpart 2は、チェーンテーブルが1->2->3->4->5->6->7->8であると仮定し、part 1={1->2->3->4}、part 2={5->6->7->8}2である.そしてpart 2を逆置き、すなわち8->7->6->53とする.そしてpart 1[0]->part 2[0],part 2[0]->part 1[1],part 1[1]->part 2[1]...すなわち、ipart 2[i]part 2[i]->part 1[i+1]i++実装コード:
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void ReorderList(ListNode head)
{
if(head == null || head.next == null || head.next.next == null){
return;
}
var p = head;
var q = head;
while(q.next.next != null){
while(p.next.next != null){
p = p.next;
}
// point head to last
var t = q.next;
q.next = p.next;
// point last to 2nd and set the second last to null
p.next.next = t;
// point 2nd last to null
p.next = null;
// reset p and q
p = t;
q = t;
if(q.next == null){
break;
}
}
}
}
解法二:本実装は接続を参照した.http://www.acmerblog.com/reorder-list-leetcode-6088.html1.slowとfastポインタを使用してチェーンテーブルを2つの部分に分け、part 1とpart 2は、チェーンテーブルが1->2->3->4->5->6->7->8であると仮定し、part 1={1->2->3->4}、part 2={5->6->7->8}2である.そしてpart 2を逆置き、すなわち8->7->6->53とする.そしてpart 1[0]->part 2[0],part 2[0]->part 1[1],part 1[1]->part 2[1]...すなわち、i
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void ReorderList(ListNode head)
{
if(head == null || head.next == null || head.next.next == null){
return;
}
var slow = head;
var fast = head;
while(fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
var mid = slow.next;
var last = mid;
ListNode pre = null;
while(last != null){
ListNode next = last.next;
last.next = pre;
pre = last;
last = next;
}
slow.next = null;
while(head != null && pre != null)
{
var next1 = head.next;
head.next = pre;
pre = pre.next;
head.next.next = next1;
head = next1;
}
}
}