0143. Reorder List

# 143. Reorder List#

## 题目 #

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.

``````

## 代码 #

``````
package leetcode

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/

// 解法一 单链表
}

// 寻找中间结点
for p2.Next != nil && p2.Next.Next != nil {
p1 = p1.Next
p2 = p2.Next.Next
}

// 反转链表后半部分  1->2->3->4->5->6 to 1->2->3->6->5->4
preMiddle := p1
preCurrent := p1.Next
for preCurrent.Next != nil {
current := preCurrent.Next
preCurrent.Next = current.Next
current.Next = preMiddle.Next
preMiddle.Next = current
}

// 重新拼接链表  1->2->3->6->5->4 to 1->6->2->5->3->4
p2 = preMiddle.Next
for p1 != preMiddle {
preMiddle.Next = p2.Next
p2.Next = p1.Next
p1.Next = p2
p1 = p2.Next
p2 = preMiddle.Next
}
}

// 解法二 数组
length := len(array)
if length == 0 {
}
for i := 0; i < len(array)/2; i++ {
tmp := &ListNode{Val: array[length-1-i], Next: cur.Next}
cur.Next = tmp
cur = tmp.Next
last = tmp
}
if length%2 == 0 {
last.Next = nil
} else {
cur.Next = nil
}
}

array := []int{}
return array
}
for cur != nil {
array = append(array, cur.Val)
cur = cur.Next
}
return array
}

``````

Sep 6, 2020