328. 奇偶链表

本题来自 LeetCode：328. 奇偶链表^[1]

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:

输入: 1-2-3-4-5-NULL
输出: 1-3-5-2-4-NULL

示例 2:

输入: 2-1-3-5-6-4-7-NULL
输出: 2-3-6-7-1-5-4-NULL

说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

解法一

题目分析

只需用两个链表分别存储奇节点和偶节点即可。

题目解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode oddHead = new ListNode(-1);
        ListNode evenHead = new ListNode(-1);

        ListNode odd = oddHead;
        ListNode even = evenHead;

        ListNode cur = head;
        while(cur != null) {
            // 连接奇节点
            odd.next = cur;
            odd = odd.next;
            cur = cur.next;
            // 连接偶节点
            if(cur != null) {
                even.next = cur;
                even = even.next;
                cur = cur.next;
            }
        }
        // 偶链表尾节点置null
        even.next = null;
        // 奇链表尾节点链表偶链表
        odd.next = evenHead.next;
        // 返回奇节点的头节点
        return oddHead.next;
    }
}

复杂度分析：
时间复杂度： O(n)， n为链表长度。
空间复杂度： O(1)

解法二

题目分析

解法一使用了两个额外的 头节点，也可以不用任务额外空间来解答。

题目解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {

        if(head == null || head.next == null) {
            return head;
        }
        // 由于奇链表的头节点就是head，故只需要奇链表的迭代节点即可
        ListNode odd = head;
        // 保存偶链表的头节点
        ListNode evenHead = head.next;
        // 偶链表的迭代节点
        ListNode even = evenHead;

        ListNode cur = head.next.next;

        while(cur != null) {
            // 连接奇节点
            odd.next = cur;
            odd = odd.next;
            cur = cur.next;
            // 连接偶节点
            if(cur != null) {
                even.next = cur;
                even = even.next;
                cur = cur.next;
            }
        }
        // 偶链表尾节点置null
        even.next = null;
        // 奇链表尾节点链表偶链表
        odd.next = evenHead;
        // 返回奇节点的头节点
        return head;
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(1)

参考资料

328. 奇偶链表: https://leetcode-cn.com/problems/odd-even-linked-list

原文始发于微信公众号（xiaogan的技术博客）：