143. Reorder List #

Problem #

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.

Problem Summary #

Reorder the linked list according to the specified rules: the first element and the last element are arranged together, then the second element and the second-to-last element are arranged together, then the third element and the third-to-last element are arranged together.

Solution Ideas #

The simplest method is to first store the linked list in an array, then find the middle node of the linked list and concatenate according to the rules. This has a time complexity of O(n) and a space complexity of O(n).

A better approach is to combine the operations from the previous problems: reversing a linked list and finding the middle node.

First find the middle node of the linked list, then use the interval reversal operation, such as the reverseBetween() operation in Problem 92, except that here the reversal interval is from the midpoint all the way to the end. Finally, use 2 pointers, one pointing to the head node and one pointing to the middle node, and start concatenating the final result. The time complexity of this approach is O(n), and the space complexity is O(1).

Code #


package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// Solution 1 Singly linked list
func reorderList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	// Find the middle node
	p1 := head
	p2 := head
	for p2.Next != nil && p2.Next.Next != nil {
		p1 = p1.Next
		p2 = p2.Next.Next
	}

	// Reverse the second half of the linked list  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
	}

	// Reassemble the linked list  1->2->3->6->5->4 to 1->6->2->5->3->4
	p1 = head
	p2 = preMiddle.Next
	for p1 != preMiddle {
		preMiddle.Next = p2.Next
		p2.Next = p1.Next
		p1.Next = p2
		p1 = p2.Next
		p2 = preMiddle.Next
	}
	return head
}

// Solution 2 Array
func reorderList1(head *ListNode) *ListNode {
	array := listToArray(head)
	length := len(array)
	if length == 0 {
		return head
	}
	cur := head
	last := head
	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
	}
	return head
}

func listToArray(head *ListNode) []int {
	array := []int{}
	if head == nil {
		return array
	}
	cur := head
	for cur != nil {
		array = append(array, cur.Val)
		cur = cur.Next
	}
	return array
}