328. Odd Even Linked List

題目敘述

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the linked list is in the range [0, 10**4].
• -10**6 <= Node.val <= 10**6

題目翻譯

今天有一個連結序列，其節點會是奇偶數交叉的排列方式，例如 1->2->5->4。題目需要將此序列重新排列，所有的奇數在前，後面接著所有的偶數，例如 1->5->2->4。

解法解析

解法上基本就是將原始序列分別拆成兩個奇數和偶數的序列，最後再將其連結起來。這樣的做法使用到四個變數來處理，兩個分別是記錄當前遍歷的奇偶數的位置，另外兩個則是記錄奇偶數的起始節點。

解法範例

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    var odd *ListNode = head
    var even *ListNode = head.Next
    var evenHead *ListNode = even

    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    odd.Next = evenHead
    return head
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function (head) {
    if (!head) {
        return null;
    }

    let odd = head,
        even = head.next,
        evenHead = even;

    while (even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
};

Kotlin

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun oddEvenList(head: ListNode?): ListNode? {
        if (head == null) return null

        var odd: ListNode? = head
        var even: ListNode? = head.next
        var evenHead: ListNode? = even

        while (even != null && even.next != null) {
            odd!!.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        }
        odd!!.next = evenHead
        return head
    }
}

PHP

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function oddEvenList($head)
    {
        if (is_null($head)) {
            return null;
        }

        $odd = $head;
        $even = $head->next;
        $evenHead = $even;

        while (!is_null($even) && !is_null($even->next)) {
            $odd->next = $even->next;
            $odd = $odd->next;
            $even->next = $odd->next;
            $even = $even->next;
        }
        $odd->next = $evenHead;
        return $head;
    }
}

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode | None) -> ListNode | None:
        if head is None:
            return None

        odd: ListNode = head
        even: ListNode = head.next
        evenHead: ListNode = even

        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = evenHead
        return head

Rust

Swift

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        if head == nil {
            return nil
        }

        var odd: ListNode? = head
        var even: ListNode? = head?.next
        var evenHead: ListNode? = even

        while even != nil && even?.next != nil {
            odd?.next = even?.next
            odd = odd?.next
            even?.next = odd?.next
            even = even?.next
        }
        odd!.next = evenHead
        return head
    }
}