leetCode-328:Odd Even Linked List

问题描述

给定一个链表，要求将原先链表的奇数节点连接在一起，再顺序连接原有链表的偶数节点。要求求解的时间复杂度为 O(1)， 空间复杂度为 O(n)。 题目链接：**点我**

样例输入输出

输入：[1, 2, 3, 4, 5, 6]

输出：[1, 3, 5, 2, 4, 6]

输入：[1, 2, 3]

输出：[1, 3, 2]

问题解法

此题主要是链表的应用，直接按题目要求进行求解即可。代码如下

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

        ListNode evenHead = head.next;
        ListNode p = head;
        while (p.next != null) {
            ListNode next = p.next;
            p.next = next.next;
            if (p.next == null) {
                break;
            }
            next.next = p.next.next;
            p = p.next;
        }
        
        p.next = evenHead;
        return head;
    }
}