链表｜ Leetcode 328

Leetcode 分类刷题 —— 链表类（Linked List）

1、题目

Leetcode 328. Odd Even Linked List

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

2、思路

把奇数节点串一起，把偶数节点串一起，最后把两个连成一条链表。

3、Java 代码

 class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // head 为奇链表头结点，odd 为奇链表尾节点
        ListNode odd = head;
        // p 为偶链表头结点
        ListNode p = head.next;
        // even 为偶链表尾节点
        ListNode even = p;
        while (odd.next != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = e.next;
        }
        odd.next = p;
        return head;
    }
}

参考文章：

https://leetcode.cn/problems/odd-even-linked-list/solution/guan-fang-ti-jie-de-tu-he-ta-de-dai-ma-d-khzx/