143. Reorder List

Problem

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

https://leetcode.com/problems/reorder-list/

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

The number of nodes in the list is in the range [1, 5 * 10⁴].
1 <= Node.val <= 1000

Test Cases

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """

solution_test.py下载完整源码
py
import pytest

from node import ListNode
from solution import Solution


@pytest.mark.parametrize('values, expected', [
    ([1,2,3,4], [1,4,2,3]),
    ([1,2,3,4,5], [1,5,2,4,3]),
])
class Test:
    def test_solution(self, values, expected):
        sol = Solution()
        head = self._build_list(values)
        sol.reorderList(head)
        result = self._format(head)
        assert result == expected

    def _build_list(self, values: list[int]) -> ListNode | None:
        root = ListNode()
        node = root
        for v in values:
            node.next = node = ListNode(v)

        return root.next

    def _format(self, head: ListNode | None) -> list[int]:
        values = []
        while head is not None:
            values.append(head.val)
            head = head.next

        return values

Thoughts

类似于翻转单链表。

先找到链表右半段的起点。用两个指针 p1 和 p2，从链表头开始，p1 每次走一步，p2 每次走两步。当 p2 走到链表终点时，p1 指在中间位置，也就是需要翻转的子链表的起点。

注意奇偶数长度的差异。每次可以先让 p2 走一步，如果没到头就让 p1、p2 再各走一步，否则就不动 p1 了。当 p2 走到头时，p1.next 是需要翻转的部分的第一个节点。

然后翻转右半段链表，直接一次遍历逐个节点翻转。

最后把两个半条链表归并串联起来。

Code

solution.py下载完整源码
py
from typing import Optional

from node import ListNode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # Find the start node of the right part (to be inverted).
        p1 = p2 = head
        while p2 is not None:
            p2 = p2.next
            if p2 is None:
                break
            p1 = p1.next
            p2 = p2.next

        right, p1.next = p1.next, None

        # Invert the right half list.
        prev = None
        curr = right
        while curr is not None:
            curr.next, prev, curr = prev, curr, curr.next

        right = prev

        # Merge left half and inverted right half into one.
        while right is not None:
            head.next, right.next, head, right = right, head.next, head.next, right.next

#Problem

#Test Cases

#Thoughts

#Code

Problem

Test Cases

Thoughts

Code