重排链表

1. 题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

2. 思路

拆分链表，反转后半段，合并

3. 实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    if head == nil {
        return
    }
    dummyHead := &ListNode{Next:head}
    fast := dummyHead
    slow := dummyHead
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    head1 := head
    head2 := reverse(slow.Next)
    slow.Next = nil

    dummyHead.Next = nil
    d := dummyHead
    for head1 != nil && head2 != nil {
        d.Next = head1
        head1 = head1.Next
        d = d.Next
        d.Next = head2
        head2 = head2.Next
        d = d.Next
    }
    if head1 != nil {
        d.Next = head1
    }
    if head2 != nil {
        d.Next = head2
    }

}


func reverse(head *ListNode) *ListNode {
    var prev *ListNode
    current := head
    var next *ListNode
    for current != nil {
        next = current.Next
        current.Next = prev
        prev = current
        current = next
    }
    return prev
}

4. 参考

• 143. 重排链表 - 力扣（LeetCode）