題目

給定一個(gè)單鏈表 L 的頭節(jié)點(diǎn) head ，單鏈表 L 表示為：
L0 → L1 → … → Ln - 1 → Ln
請將其重新排列后變?yōu)椋?br> L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

例：
輸入：head = [1,2,3,4]
輸出：[1,4,2,3]

方法：翻轉(zhuǎn)后半部分鏈表

思路同 234. 回文鏈表，區(qū)別在于本題在翻轉(zhuǎn)鏈表后進(jìn)行插入

• slow 表示慢指針，每次向右移動(dòng)一步；fast 表示快指針，每次向右移動(dòng)兩步。直至快指針 fast 或快指針向右移動(dòng)一步 fast.next 后不存在，即當(dāng)快指針 fast 指向鏈表尾部或尾部的下一個(gè)位置時(shí)，循環(huán)停止。那么此時(shí)，慢指針指向中部

  
  
• right 指向后半部分鏈表的首部，即需要進(jìn)行翻轉(zhuǎn)部分的首部，初始值為慢指針的下一個(gè)節(jié)點(diǎn) slow.next
• left 指向前半部分鏈表的首部，并將其前半部分尾部 slow.next 指向的節(jié)點(diǎn)設(shè)為 None，從而使得原鏈表正式分成兩個(gè)鏈表
• 對(duì)第二個(gè)鏈表進(jìn)行翻轉(zhuǎn)操作
• 循環(huán)，因?yàn)榈诙€(gè)鏈表一定比第一個(gè)鏈表短，所以通過第二個(gè)鏈表來判斷循環(huán)的停止
  • curLeft 指向第一個(gè)鏈表的當(dāng)前指向節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，為了進(jìn)行插入操作；curRight 指向第二個(gè)鏈表的當(dāng)前指向節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，為了進(jìn)行插入操作

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reorderList(self, head):
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        right = slow.next
        slow.next = None
        left = head
        right = self.reverse(right)

        while right:
            curLeft = left.next
            left.next = right
            left = curLeft

            curRight = right.next
            right.next = left
            right = curRight
        return head
    
    def reverse(self, node):
        pre = None
        while node:
            temp = node.next
            node.next = pre
            pre = node
            node = temp
        return pre

參考

代碼相關(guān)：https://programmercarl.com/0143.%E9%87%8D%E6%8E%92%E9%93%BE%E8%A1%A8.html