链表-中等：重排链表 By Swift

• 题目

给定一个单链表 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.

• 思路

寻找中间节点。
反转链表后半部分。
合并链表。

• 代码

class Solution {
    func reorderList(_ head: ListNode?) {
        if head == nil { return }
        let mid = findMiddle(head)
        let l1 = head
        var l2 = mid?.next
        mid?.next = nil
        l2 = reverse(l2)
        merge(l1, l2)
    }
    
    func findMiddle(_ head: ListNode?) -> ListNode? {
        var slow = head, fast = head
        while fast?.next != nil && fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        
        return slow
    }
    
    func reverse(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        let result = reverse(head?.next)
        head?.next?.next = head
        head?.next = nil
        return result
    }
    
    func merge(_ l1: ListNode?, _ l2: ListNode?) {
        var cur1 = l1
        var cur2 = l2
        
        while cur1 != nil && cur2 != nil {
            let cur1Next = cur1?.next
            let cur2Next = cur2?.next
            
            cur1?.next = cur2
            cur1 = cur1Next
            
            cur2?.next = cur1
            cur2 = cur2Next
        }
    }
}

文章到这里就结束了，你也可以私信我及时获取最新资料。如果你有什么意见和建议欢迎给我留言。

作者：_GodIsCoder
链接：https://juejin.cn/post/6904139986853953549