Reorder List

1. Problem Description

Given the head head of a singly linked list L, the list is represented as:

L0 → L1 → … → Ln - 1 → Ln Reorder it to:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not simply change the values inside the nodes; the nodes themselves must be relinked.

2. Approach

Split the linked list, reverse the second half, then merge the two halves.

3. Implementation

/**
 * 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. References

• 143. Reorder List - LeetCode